効率的な決定論的マルチプロセッシング（ｄｅｔｅｒｍｉｎｉｓｔｉｃｍｕｌｔｉｐｒｏｃｅｓｓｉｎｇ）

专利摘要:
マルチプロセッシングシステムにおいて、マルチスレッドアプリケーションのスレッドによって実行される操作の順序を制御するためのハードウェアおよび／またはソフトウェアファシリティが提供される。ファシリティは、マルチスレッドアプリケーションに同じ入力が与えられると、マルチプロセッシングシステムが操作を決定論的にインターリーブし、それによってマルチスレッドアプリケーションが実行されるたびに同じ出力を生成するように、マルチスレッドアプリケーションの実行をシリアル化または選択的にシリアル化することができる。ファシリティは、マルチスレッドアプリケーションコードの実行を、決定論的操作数を指定する２つ以上の量子に分割し、スレッドが２つ以上の量子を実行する決定論的順序を指定する。決定論的操作数は、マルチスレッドアプリケーションのクリティカルパスに従うように構成され得る。指定されたメモリ操作は、証明可能にローカルなデータにアクセスするものなど、決定論的順序にかかわらず、実行され得る。ファシリティは、識別されたバグ情報の動的なバグ回避および共有を提供することができる。
公开号:JP2011515000A
申请号:JP2010550845
申请日:2009-03-11
公开日:2011-05-12
发明作者:オスキン，マーク・エイチ；セゼ，ルイス；デヴィエッティ，ジョセフ・ルーク；ルシア，ブランドン・マイケル
申请人:ユニバーシティ・オブ・ワシントン；
IPC主号:G06F9-46

专利说明:

[0001] 本願の実施例は、例えば、効率的な決定論的マルチプロセッシングに関する。]
背景技術

[0002] 本出願は、参照により本明細書に組み込まれる２００８年３月１１日出願の「Ａ ＭＥＴＨＯＤＦＯＲ ＥＦＦＩＣＩＥＮＴＤＥＴＥＲＭＩＮＩＳＴＩＣ ＭＵＬＴＩＴＨＲＥＡＤＩＮＧ（効率的な決定論的マルチスレッディングのための方法）」という名称の米国特許仮出願第６１／０３５，４９０号の利益を主張する。本出願は、参照により本明細書に組み込まれる２００７年１２月１２日出願の「ＤＥＴＥＲＭＩＮＩＳＴＩＣ ＭＵＬＴＩＰＲＯＣＥＳＳＩＮＧ（決定論的マルチプロセッシング）」という名称の米国特許仮出願第６１／０１３，０１９号の利益を主張する２００８年１２月１２日出願の「ＤＥＴＥＲＭＩＮＩＳＴＩＣ ＭＵＬＴＩＰＲＯＣＥＳＳＩＮＧ（決定論的マルチプロセッシング）」という名称の米国特許出願第１２／３３４，３３６号に関連する。]
[0003] マルチプロセッシングは、２つ以上の処理装置がそれぞれ１つまたは複数のプロセス（プログラムまたは命令のセット）を同時に実行する動作モードである。マルチプロセッシングシステムの目的は、処理速度を向上させることである。通常、これは、各処理装置が同じプロセスの異なる命令のセットまたは異なるスレッドを処理することによって達成される。プロセスは、１つまたは複数のスレッドを実行することができる。各スレッドは、それ自体のプログラムコンテキストを含むそれ自体のプロセッサコンテキストを有する。従来、アプリケーションがマルチプロセッシングの利益を利用するためには、ソフトウェア開発者は、アプリケーションをマルチスレッド型で書く必要がある。本明細書で使用する場合、マルチスレッドアプリケーションとは、２つ以上のスレッドを同時に実行することができるプログラムを指す。]
[0004] マルチプロセッサまたはマルチコアシステム（まとめて「マルチプロセッシングシステム」と呼ぶ）において、マルチスレッドアプリケーションの２つ以上のスレッドは同時に実行することができ、各プロセッサまたはコアが特定のスレッドを実行する。マルチスレッドアプリケーションのスレッドが、同時実行中に、例えばメモリなどリソースを共有することは、一般的である。本明細書で使用される場合、同時実行とは、マルチスレッドアプリケーションの２つ以上のスレッドの同時の実行を指す。同時実行の結果、マルチスレッドアプリケーションの２つ以上のスレッドが同じ共有リソースを読み取り、および／または更新することができる。例えば、あるスレッドは、共有メモリロケーションの値を変更することができ、一方、別のスレッドは、共有メモリロケーションに格納された値に応じて、一連の操作を実行する。]
[0005] 従来のソフトウェア開発モデル下で、ソフトウェア開発者は、そのマルチスレッドアプリケーション内の並列スレッドを識別し、正しく同期しようと試みることにかなりの時間量を費やす。例えば、開発者は、ロック、セマフォ、バリア、または他の同期機構を明示的に使用して、共有リソースへのアクセスを制御することができる。スレッドが共有リソースにアクセスするとき、同期機構は、リソースが使用可能になるまで、これらのスレッドを一時停止することによって、他のスレッドがリソースにアクセスするのを防ぐ。同期機構を明示的に実装するソフトウェア開発者は、通常、同期コードをデバッグするのにもかなりの時間量を費やす。しかし、通常、同期エラーに起因するソフトウェアの欠陥（バグとも呼ばれる）が一時的に表面化する（すなわち、インターリーブされたスレッド操作の特定のシーケンスにのみバグが現れる可能性がある）。その結果、欠陥のあるソフトウェアは、小さな同期バグが現れる前に、何百回も正しく実行する可能性がある。]
[0006] こうしたシステムにおけるスレッドの様々なインターリービングによって非決定論的挙動が作り出されるため、マルチプロセッシングシステムのためのソフトウェアを開発することは難しい。インターリービングとは、スレッド間の対話を含み得るスレッド操作の順序を指す。スレッド間の可能なインターリービングの数は、スレッドの数が増すにつれて、著しく増す。その結果、マルチスレッドアプリケーションは、誤り検出およびモデリングプログラムの挙動に関して、追加の問題を提示する。例えば、マルチスレッドアプリケーションに同じ入力が与えられると、マルチプロセッシングシステムは、スレッド操作を非決定論的にインターリーブし、それによって、マルチスレッドアプリケーションが実行されるたびに異なる出力を生成する。図１は、マルチプロセッシングシステムにおいて実行されるマルチスレッドアプリケーションにおける２つの可能なスレッドインターリービングの例を示す高レベル図である。図示されるように、アプリケーションは、少なくとも２つのスレッド、スレッド１およびスレッド２を含む。アプリケーションが呼び出されると、ある時点で、スレッド１は、変数Ａの値を１に設定する（Ａ＝１）操作、次いで変数Ｂの値を変数Ａの値に設定する（Ｂ＝Ａ）操作を実行し、スレッド２は、変数Ｂの値をゼロに設定する（Ｂ＝０）操作、次いで変数Ａの値を変数Ｂの値に設定する（Ａ＝Ｂ）操作を実行する。図示されるように、スレッド１およびスレッド２の操作は、非決定論的にインターリーブされ、それによって、アプリケーションが呼び出されるたびに、異なる出力を生成する。すなわち、最初に示された呼び出し中、操作のインターリービングによって変数ＡおよびＢがそれぞれゼロに設定され、２番目に示された呼び出し中、操作のインターリービングによって変数ＡおよびＢがそれぞれ１に設定された。] 図１
[0007] マルチスレッド実行における非決定性は、例えば、他のプロセスが同時に実行する、オペレーティングシステムリソースの割り当てにおける差、キャッシュの状態、トランスレーションルックアサイドバッファ（「ＴＬＢ」）、バス、割り込み、および他のマクロアーキテクチャ構造など、実行環境におけるわずかな変化に起因し得る。]
発明が解決しようとする課題

[0008] その結果、マルチスレッドアプリケーションを開発することは、シングルスレッドアプリケーションを開発するよりかなり難しい。]
課題を解決するための手段

[0009] 従来、この問題に対処するにあたっての取り組みは、以前生成されたログファイルに基づいてマルチスレッド実行を決定論的に再生することに焦点を当てていた。しかし、決定論的再生システムは、再生ログファイルの維持に伴うオーバーヘッドの結果、かなりの性能の低下を受ける。さらに、決定論的再生では、ソフトウェア開発者は、スレッドのインターリービングがどのように実行されるかを制御しない。その結果、ソフトウェアが顧客に配布される前に、操作の特定のインターリービングに起因する同期バグは、識別（およびより重要には修正）されない場合がある。非決定性は、テストカバレージを評価するのを難しくする点で、ソフトウェア開発プロセスをさらに複雑にする。良好なカバレージは、広範なプログラム入力と、広範な可能なスレッドインターリービングとを必要とする。]
[0010] ファシリティの１つまたは複数の実施形態が、添付の図面の図に例として、かつ限定されないものとして示されている。図中、参照番号は、類似の要素を示す。]
図面の簡単な説明

[0011] マルチスレッドプログラムにおける、２つの可能なスレッドインターリービングの一例を示す高レベル図である。
１つまたは複数の実施形態における、ファシリティによって実行される決定論的シリアル化プロセスのフロー図である。
１つまたは複数の実施形態における、ファシリティによって実行される決定論的選択的シリアル化プロセスのフロー図である。
１つまたは複数の実施形態における、ファシリティが実行するコンピューティングシステムのアーキテクチャ例を示す高レベルブロック図である。
１つまたは複数の実施形態における、決定論的マルチプロセッシングシステムの様々な機能的要素を示す高レベルブロック図である。
１つまたは複数の実施形態における、マルチプロセッサコードを決定論的にするためにファシリティによって使用されるデータ構造を示す高レベルブロック図である。
１つまたは複数の実施形態における、スレッドを作成し、決定論的に実行する一例を示す高レベル図である。
１つまたは複数の実施形態における、マルチプロセッサコードを決定論的にするためにトランザクショナルメモリシステムを使用する一例を示す高レベルブロック図である。
１つまたは複数の実施形態における、アプリケーションを増補（augment）するためにファシリティによって実行されるプロセスを示すフロー図である。
１つまたは複数の実施形態における、ブロックを構文解析するためにファシリティによって実行されるプロセスを示すフロー図である。
１つまたは複数の実施形態における、マルチスレッドアプリケーションの増補された機能の制御フローグラフの一例である。
１つまたは複数の実施形態における、決定論的マルチプロセッシング初期化関数を示すフロー図である。
１つまたは複数の実施形態における、決定論的マルチプロセッシングコミット関数を示すフロー図である。
１つまたは複数の実施形態における、共有テーブルを示す高レベルブロック図である。
１つまたは複数の実施形態における、マルチスレッドアプリケーションのアドレス空間におけるメモリロケーションごとのマスクを示す高レベルブロック図である。
１つまたは複数の実施形態における、ファシリティによって実行される適応量子プロセス（adaptive quanta process）を示すフロー図である。
１つまたは複数の実施形態における、共有メモリデータ構造へのアクセスに伴うオーバーヘッドを低減するためにファシリティによって実行されるプロセスのフロー図である。
１つまたは複数の実施形態における、仮想マシン内のマルチスレッドアプリケーションのスレッドの実行を決定論的に制御するために決定論的マルチプロセッシングシステムと共に実行するＶＭＭを示す高レベルブロック図である。
１つまたは複数の実施形態における、ファシリティによって実行される監視プロセスのフロー図である。
１つまたは複数の実施形態における、バグアグリゲータサービス（bug aggregator service）を示す高レベルデータフロー図である。
１つまたは複数の実施形態における、トランザクショナルメモリフォワーディング（transactional memory forwarding）の一例を示す高レベル図である。
１つまたは複数の実施形態における、ファシリティによって実行されるトランザクショナルメモリフォワーディングプロセスを示すフロー図である。
１つまたは複数の実施形態における、バグファインダウェブサービス（bug finder web service）を示す高レベルデータフロー図である。
１つまたは複数の実施形態における、ファシリティによって実行されるバグファインダプロセスのフロー図である。
図２５Ａは、１つまたは複数の実施形態における、決定論的マルチプロセッシングシステムの様々な機能的要素を示す高レベルブロック図である。] 図２５Ａ
[0012] 図２５Ｂは、１つまたは複数の実施形態における、決定論的マルチプロセッシングシステムの様々な機能的要素を示す高レベルブロック図である。] 図２５Ｂ
[0013] 図２５Ｃは、１つまたは複数の実施形態における、決定論的マルチプロセッシングシステムの様々な機能的要素を示す高レベルブロック図である。] 図２５Ｃ
実施例

[0014] 決定論的再生システムなどの従来のシステムは、マルチスレッドアプリケーションの開発における非決定論的挙動に伴う問題を適切に解決しない。さらに、既存のシステムは、マルチスレッドアプリケーションの配置における非決定論的挙動に伴う問題を低減することも、解決しようと試みることもない。したがって、マルチスレッドアプリケーションの決定論的マルチプロセッシングのためのハードウェアおよび／またはソフトウェアファシリティ（「ファシリティ」）が開発された。本明細書で使用される場合、決定論的マルチプロセッシングという用語は、マルチスレッドアプリケーションに同じ入力が与えられると、マルチスレッドアプリケーションによって同じ出力が生成される技術を指す。例えば、共有リソースへのスレッドアクセスを同期するための負担から開発者を解放することによって、ファシリティは、マルチスレッドアプリケーションを開発する処理を簡略化する。さらにファシリティは、こうしたマルチスレッドアプリケーションが配置されるとき、例えば、開発者がバグを再生し、様々なスレッドインターリービングを厳格にテストできるようにすることによって、マルチスレッドアプリケーションの信頼性を向上させる。]
[0015] いくつかの実施形態において、ファシリティは、マルチスレッドアプリケーションの実行を決定論的な有限数の操作の組（各組は、本明細書では「量子」と呼ばれる）に分割する。量子を識別するとき、ファシリティは、例えば、通信無しのスレッド操作など、並行して実行され得る操作と、スレッド間通信、システムコールなど、決定論的な順序で実行されるべき操作とを区別することができる。次いで、ファシリティによって識別される各量子は、決定論的順序で実行される。マルチスレッドアプリケーションのスレッドによって量子が実行される順序を制御することによって、ファシリティは、マルチスレッドアプリケーションが決定論的に挙動できるようにする。すなわち、同じ入力が与えられると、マルチスレッドアプリケーションのスレッドは、その操作を決定論的にインターリーブし、それによって同じ出力を提供する。いくつかの実施形態では、量子サイズ（すなわち、予め定義された数の操作）はスレッド間で異なり、一方、他の実施形態では、量子サイズは均一である。]
[0016] いくつかの実施形態において、ファシリティは、マルチスレッドアプリケーションの実行をシリアル化する。すなわち、ファシリティは、すべてのスレッド操作のグローバルなインターリービングを制御することができる。例えば、これは、量子境界に到達したとき、スレッド間に決定論的順序で渡されるメモリアクセストークンを確立することによって達成され得る。スレッドは、トークンの値がそのスレッドの識別子に一致するとき、トークンを「保持する」と呼ばれ得る。トークンの値がスレッドの識別子に一致しないとき、トークンの値がスレッドの識別子に一致するまで、その実行は一時停止される。トークンの値がスレッドの識別子に一致するとき、スレッドは、トークンが次のスレッドに渡される前に、決定論的な有限数の操作（すなわち量子）を実行する。例えば、決定論的順序で次のスレッドの識別子に対応するように、トークンの値を進めることによって、トークンは、次のスレッドに渡され得る。]
[0017] 図２は、１つまたは複数の実施形態における、ファシリティによって実行される決定論的シリアル化プロセス２００のフロー図である。例えば、決定論的シリアル化プロセス２００は、マルチスレッドアプリケーションがマルチプロセッシングシステム上で実行している間に実行され得る。マルチスレッドアプリケーションが実行している間、ファシリティは、スレッドごとにステップ２０５〜２１５をループする。ステップ２０５で、トークンの値がスレッドの識別子に一致することをファシリティが決定した場合、ファシリティはステップ２１０に進み、そうでない場合、ファシリティは折り返してステップ２０５に戻る。すなわち、ファシリティは、トークンの値がそのスレッドの識別子に一致するまで、スレッドの実行を一時停止する。ステップ２１０で、ファシリティは、識別子がトークンに一致するスレッドが決定論的な有限数の操作（すなわち量子）を実行できるようにし、次いでファシリティは、ステップ２１５に進む。ステップ２１５で、ファシリティは、トークンの値を、決定論的な順序で次のスレッドの識別子に等しくなるように設定し、次いでファシリティは、ステップ２０５に進む。ファシリティは、アプリケーションが終了するまで、シリアル化プロセス２００をループし続けることができることに留意されたい。] 図２
[0018] 図２および以下のフロー図のそれぞれに示されるステップは様々な方法で変更され得ることを、当業者であれば理解されたい。例えば、いくつかのステップの順序が並べ替えられてもよく、いくつかのサブステップが並行して実行されてもよく、いくつかの示されたステップが省略されてもよく、または他のステップが含まれていてもよい。] 図２
[0019] いくつかの実施形態において、ファシリティは、マルチスレッドアプリケーションの実行を選択的にシリアル化する。すなわち、ファシリティは、他のスレッド操作が並行して実行される間に、いくつかのスレッド操作のインターリービングを制御する（本明細書では「制御された操作」と呼ばれる）ことができる。例えば、ファシリティは、２つ以上のスレッド間の通信を伴う操作のインターリービングを制御することができる。スレッド間通信は、スレッドが別のスレッドによってプライベートに保持されるデータを読み取るとき、またはスレッドが共有データに書き込み、それをプライベート化するときに起こる。いくつかの実施形態において、スレッドが別のスレッドによってプライベートに保持されるとみなされるデータを読み取ろうと試みるとき、スレッドは、トークンの値がその識別子に一致し、すべての他のスレッドがその実行における決定論的ポイントに到達する（例えば、量子の実行を終了する、ブロックされるなど）まで、その実行を一時停止する。同様に、いくつかの実施形態において、スレッドは、共有される、または別のスレッドによってプライベートに保持されるとみなされるデータに書き込もうと試みるとき、トークンの値がその識別子に一致し、すべての他のスレッドがその実行における決定論的ポイントに到達するまで、その実行を一時停止する。その結果、ファシリティは、すべてのスレッドが、その実行での決定論的ポイントにおけるデータの状態の変化（共有からスレッドによってプライベートに保持されるまで）を観察することを確実にする。]
[0020] いくつかの実施形態において、スレッド間通信を検出するために、ファシリティは、マルチスレッドアプリケーションのアドレス空間におけるメモリロケーションごとに、共有情報を含む共有メモリデータ構造を維持する。例えば、こうした情報は、メモリロケーションが共有である、プライベートであるなどを示すことができる。共有は、操作レベル、命令レベル、ページレベルなど、様々なレベルで起こり得ることに留意されたい。いくつかの実施形態において、スレッドは、それ自体のプライベートに保持されたデータにアクセスすることも、トークンを保持することなく共有データを読み取ることもできる。しかし、共有データに書き込むために、または別のスレッドによってプライベートとして保持されるデータを読み取るために、スレッドは、トークンを保持し、すべての他のスレッドがその実行における決定論的ポイントに到達するまで待つ。スレッドが、別のスレッドによってプライベートとみなされるメモリロケーションを読み取るとき、共有メモリデータ構造は、読み取られたメモリロケーションを共有されたものとみなすべきであることを示すために更新される。スレッドがメモリロケーションに書き込むとき、メモリロケーションをそのスレッドによってプライベートに保持されているものとみなすべきであることを示すために、共有メモリデータ構造が更新される。同様に、スレッドが別のスレッドによってこれまではアクセスされていないメモリロケーションを読み取るとき、共有メモリデータ構造は、メモリロケーションをそのスレッドによってプライベートに保持されているものとみなすべきであることを示すために更新される。]
[0021] いくつかの実施形態において、ファシリティは、共有メモリデータ構造を共有テーブルとして実装する。図１４は、いくつかの実施形態における、共有テーブル１４００を示す高レベルブロック図である。共有テーブル１４００は、マルチスレッドアプリケーションのアドレス空間におけるメモリロケーション１４０５ごとの共有情報を維持する。共有は、操作レベル、命令レベル、ページレベルなど、様々なレベルで起こり得ることに留意されたい。共有テーブル１４００は、メモリロケーション１４０５ごとに、そのロケーションに格納されるデータにアクセスした２つ以上のスレッドを識別する共有データフィールド１４１０を含む。例えば、示された実施形態において、共有データフィールド１４１０は、メモリロケーションＢに格納されたデータは、スレッド１、スレッド２、およびスレッド６によってアクセスされたことを示す。共有テーブル１４００は、メモリロケーション１４０５ごとに、そのロケーションに格納されたデータがプライベートとみなされるスレッドを識別するプライベートデータフィールド１４１５を含む。例えば、示された実施形態において、プライベートデータフィールド１４１５は、メモリロケーションＡおよびＣがスレッド２に対してプライベートとみなされるデータを格納することを示す。] 図１４
[0022] ファシリティが共有メモリデータ構造を様々な形で実装することができることを、当業者であれば理解されたい。例えば、いくつかの実施形態において、共有メモリデータ構造は、メモリロケーションごとに、そのメモリロケーションにアクセスしたすべてのスレッドを識別するビットマスクとして実装される。図１５は、１つまたは複数の実施形態における、マルチスレッドアプリケーションのアドレス空間におけるメモリロケーション１５０５ごとのスレッドマスク１５００を示す高レベルブロック図である。メモリロケーション１５０５は、その対応するスレッドマスク１５００が単一のスレッド１５１０を識別するとき、プライベートとみなされる。例えば、メモリロケーションＡおよびメモリロケーションＣは、それらの対応するマスク１５００ａおよび１５００ｃがスレッド２のみを識別するため、スレッド２に対してプライベートとみなされる。メモリロケーション１５０５は、その対応するスレッドマスク１５００が２つ以上のスレッド１５１０を識別するとき、共有とみなされる。例えば、メモリロケーションＢは共有とみなされる。というのは、その対応するスレッドマスク１５００ｂがスレッド１、スレッド２、およびスレッドを識別するからである。スレッド１５１０の数は、アプリケーション間および／またはアプリケーションの状態間で変わり得ることに留意されたい。したがって、示した実施形態に示されるように、８つのスレッドの例は制限とみなされるべきではない。] 図１５
[0023] 図３は、１つまたは複数の実施形態における、ファシリティによって実行される決定論的選択的シリアル化プロセス３００のフロー図である。例えば、スレッドまたはプロセッサが、メモリ操作、システムコールなど、制御された操作を実行しようと試行すると、選択的シリアル化プロセス３００が実行され得る。ステップ３０５で、操作がシステムコールである（例えばＩ／Ｏ操作など）ことをファシリティが決定した場合、ファシリティはステップ３２５に進み、そうでない場合、ファシリティはステップ３１０に進む。ステップ３１０で、操作がスレッドによってプライベートに保持されていないメモリにアクセスするとファシリティが決定した場合、ファシリティはステップ３１５に進み、そうでない場合、ファシリティはステップ３５５に進む。ステップ３１５で、操作が共有メモリにアクセスしたことをファシリティが決定した場合、ファシリティはステップ３２０に進み、そうでない場合、ファシリティはステップ３２５に進む。ステップ３２０で、操作が格納操作であることをファシリティが決定した場合、ファシリティはステップ３２５に進み、そうでない場合、ファシリティはステップ３５５に進む。ステップ３２５で、トークンの値がスレッドの識別子に一致することをファシリティが決定した場合、ファシリティはステップ３３０に進み、そうでない場合、ファシリティは折り返してステップ３２５に戻る。すなわち、ファシリティは、トークンの値が選択されたスレッドの識別子に一致するまで、選択されたスレッドの実行を一時停止する。ステップ３３０で、マルチスレッドアプリケーションのすべてのスレッドが一時停止（またはブロック）されたことをファシリティが決定した場合、ファシリティはステップ３３５に進み、そうでない場合、ファシリティは折り返してステップ３３０に戻る。トークンを保持するスレッドが実行し得る前に、すべてのスレッドが一時停止されるのを待つことによって、ファシリティは、実行における決定論的ポイントで、すべてのスレッドが操作の実行に起因する任意の状態の変化を観察することを確実にする。ステップ３３５で、操作がシステムコールであることをファシリティが決定した場合、ファシリティはステップ３５５に進み、そうでない場合、ファシリティはステップ３４０に進む。ステップ３４０で、操作が格納操作であることをファシリティが決定した場合、ファシリティはステップ３４５に進み、そうでない場合、ファシリティはステップ３５０に進む。ステップ３４５で、ファシリティは、操作によって影響を受けるメモリロケーションを、スレッドによってプライベートに保持されているものとみなすべきであることを示すために、共有メモリデータ構造を更新し、次いで、ファシリティはステップ３５５に進む。ステップ３５０で、ファシリティは、操作によってアクセスされたメモリロケーションを共有されたものとみなすべきであることを示すために、共有メモリデータ構造を更新し、次いでファシリティはステップ３５５に進む。ステップ３５５で、ファシリティによって、スレッドは操作を始めることができ、次いでファシリティは戻る。] 図３
[0024] いくつかの実施形態において、ファシリティは、トランザクショナルメモリシステムと共に動作して、マルチスレッドアプリケーションの実行をシリアル化または選択的にシリアル化する。例えば、ファシリティは、トランザクショナルメモリシステムを使用して、メモリ操作の決定論的順序を侵害することになるスレッド間通信を検出することができる。すなわち、共有メモリデータ構造の代わりに、またはそれに加えて、トランザクショナルメモリシステムが使用され得る。トランザクショナルメモリシステムは、ハードウェアトランザクショナルメモリ（ＨＴＭ）システム、ソフトウェアトランザクショナルメモリ（ＳＴＭ）システム、またはハイブリッドハードウェア−ソフトウェアトランザクショナルメモリシステム（ＨＳ−ＴＭ）とすることができることに留意されたい。トランザクショナルメモリシステムと共に動作するとき、ファシリティは、スレッドによって実行される各量子をトランザクション内に封入する。各量子をトランザクション内に封入することによって、スレッドは、アトミック的に、かつ隔離されて実行するようにみえる。その結果、トランザクションは、並行して実行され、次いで、決定論的順序に従ってコミットされ得る。すなわち、ＴＭシステムは、スレッドがトークンを保持するとき、トランザクションをコミットし、トランザクションがコミットされた後、トークンは、決定論的順序で次のスレッドに渡される。いくつかの実施形態において、ファシリティが複数のトークンをサポートし、それによって、各プロセス内のスレッド間に渡されるトークンをそれぞれ指定する複数の決定論的プロセスが同時に実行できるようになることに留意されたい。通常、トランザクションは、決定論的順序を侵害することになる（本明細書では「競合」と呼ばれる）スレッド間通信を含む場合、コミットされない。競合が存在するとき、トランザクションは、中止され、再開され得る。]
[0025] いくつかの実施形態において、ファシリティは、量子ビルダコンポーネント（quantum builder component）、および決定論的マルチプロセッシング（「ＤＭＰ」）コンポーネントを含む。例えば、図２５Ａ〜２５Ｃは、いくつかの実施形態において決定論的マルチプロセッシングシステム２５００の様々な機能的要素を示す高レベルブロック図である。図２５Ａは、量子ビルダコンポーネント２５０５およびＤＭＰコンポーネント２５１０を含むＤＭＰシステム２５００ａを示す。量子ビルダコンポーネント２５０５は、マルチスレッドアプリケーションの実行を量子（すなわち、決定論的な有限数の操作の組）に分割するために使用される。いくつかの実施形態において、量子ビルダ２５０５コンポーネントは、例えば通信無しのスレッド操作など、並行して実行され得る操作と、スレッド間通信、システムコールなど、決定論的な順序で実行されるべき操作（例えば、制御された操作）とを区別する。ＤＭＰコンポーネント２５１０は、決定論的順序に従って各量子が実行されることを確実にする。例えば、マルチスレッドアプリケーションの実行をシリアル化するために、ＤＭＰコンポーネント２５１０は、量子境界に到達したとき、決定論的順序でスレッド間に渡されるトークンを実装することができる。別の例として、マルチスレッドアプリケーションの実行を選択的にシリアル化するために、ＤＭＰコンポーネント２５１０は、トークンを保持することなく、スレッドが操作を実行することができるかどうかを決定するために使用される共有メモリデータ構造を実装することができる。図２５Ｂは、共有メモリデータ構造２５２０を含むＤＭＰシステム２５００ｂを示す。さらに別の例として、共有メモリデータ構造２５２０の代わりに、またはそれに加えて、トランザクショナルメモリシステムが使用され得る。図２５Ｃは、量子ビルダコンポーネント２５０５およびＤＭＰコンポーネント２５１０と共に動作して、マルチスレッドアプリケーションの実行をシリアル化または選択的にシリアル化し得るトランザクショナルメモリシステム２５２５を含むＤＭＰシステム２５００ｃを示す。トランザクショナルメモリシステム２５２５は、ハードウェアトランザクショナルメモリ（ＨＴＭ）システム、ソフトウェアトランザクショナルメモリ（ＳＴＭ）システム、またはハイブリッドハードウェア−ソフトウェアトランザクショナルメモリシステム（ＨＳ−ＴＭ）とすることができる。] 図２５Ａ 図２５Ｂ 図２５Ｃ
[0026] いくつかの実施形態において、トークンがブロックされた（例えば、別のスレッドによって保持されたロックを待つ）スレッドに進められると、ファシリティは、トークンを次のスレッドに渡し、それによって、開発者がマルチスレッドコード内に含まれる同期プリミティブのブロックに起因するライブロックを回避する。例えば、トークンがスレッド２に渡されるときにスレッド２が進むために必要とするロックをスレッド１が保持する場合、トークンは、次のスレッド（例えば、スレッド３）に渡される。トークンが決定論的順序で渡されるため、また各スレッドが量子を実行する（またはトークンを渡す）ため、量子は、決定論的にインターリーブされ、それによってライブロックを防ぎ、コードが同じ入力で実行されるたびに同じ出力を生成する。]
[0027] 量子ビルダコンポーネント２５０５およびＤＭＰコンポーネント２５１０は、ハードウェア、ソフトウェア、またはハードウェアおよびソフトウェアの組み合わせにおいて実装され得る。例えば、量子ビルダコンポーネント２５０５は、命令が後退するにつれてそれらをカウントし、所定の量子サイズに到達したとき、量子境界を配置することによって実装され得る。実行をシリアル化するために、ＤＭＰコンポーネント２５１０は、決定論的順序で量子境界においてプロセッサ間に渡されるトークンとして実装され得る。別の例として、実行を選択的にシリアル化するために、量子ビルダコンポーネント２５０５は、アクセスがスレッド間通信を伴うかどうか（例えば、共有データへのアクセスなど）を決定するために、メモリアクセスを監視することができる。一実施形態において、ＤＭＰコンポーネント２５１０は、共有メモリデータ構造２５２０を実装するために、ＭＥＳＩ（「変更、排他、共有、無効」）キャッシュコヒーレンスプロトコルによって維持されるキャッシュライン状態を使用する。排他または変更状態のキャッシュラインは、プロセッサによってプライベートに保持されるものとみなされ、トークンを保持しないそれ自体のスレッドによって自由に読み取られ、または書き込まれ得る。同様に、共有状態のキャッシュラインは、トークンを保持しないそれ自体のスレッドによって自由に読み取られ得る。すべてのスレッドがその実行における決定論的ポイントにあるとき（例えば、すべてのプロセッサがブロックされ、または量子境界に到達したとき）、およびプロセッサが決定論的トークンを取得したとき、プロセッサは、共有状態のキャッシュラインに書き込むことができる。こうした実施形態において、各プロセッサは、それがブロックされ、および／またはブロック解除されると、ブロードキャストする。任意のプロセッサによってキャッシュに入れられないラインに対応する共有メモリデータ構造２５２０におけるエントリの状態は、メモリに保持され、メモリコントローラによって管理することができ、こうしたエントリの状態は、キャッシュミスが処理されるときに転送され得ることに留意されたい。]
[0028] いくつかの実施形態において、ファシリティは、コンパイラまたはバイナリ書き換えインフラストラクチャを使用して実装され得る。例えば、量子ビルダコンポーネント２５０５は、マルチスレッドアプリケーションコード内に同期コードを挿入し、コンパイラによって生成される制御フローグラフ（「ＣＦＧ」）において操作を追跡することによって、コンパイラを使用して量子を構築することができる。量子は、サイズが決定論的である限り、均一サイズのものである必要はないことに留意されたい。こうした同期コードは、例えば、関数呼び出しの最初および最後、およびＣＦＧ後退エッジの最後に挿入することができる。挿入されたコードは、量子サイズを追跡し、ターゲットサイズに到達したとき、ＤＭＰコンポーネント２５１０にコールバックする。いくつかの実施形態において、ファシリティは、ソースコード、ソースコードの中間表現、または実行ファイルを増補する。いくつかの実施形態において、挿入されたコードは、１つまたは複数の決定論的マルチプロセッシング（「ＤＭＰ」）関数および／またはデータ構造を含む。挿入されたＤＭＰ関数は、１つまたは複数のデータ構造（例えば、共有メモリデータ構造２５２０）を維持する、ＤＭＰコンポーネント２５１０によって提供され得るランタイムシステムにコールバックすることができる。増補されたコードがマルチプロセッシングシステムによって実行されると、挿入されたＤＭＰ関数およびデータ構造は、次いで、メモリおよびＩ／Ｏ操作、システムコールなど、操作が実行される順序を制御するために使用される。スレッドがこうした動作を実行する順序を制御することによって、ファシリティは、マルチスレッドアプリケーションが決定論的に挙動できるようにする。すなわち、同じ入力が与えられると、マルチスレッドアプリケーションのスレッドは、操作の一部またはすべてを決定論的にインターリーブし、それによって同じ出力を提供することができる。ファシリティは他のスレッド操作を制御するように拡張され得ることを、当業者であれば理解されたい。]
[0029] いくつかの実施形態において、コードが増補された後、コンパイラは、例えば、ＤＭＰライブラリに対するすべての呼び出しをインライン化するなど、コードを再度最適化する。コンパイラは、本明細書では具体的に記載しないが、増補されたコードに対して他の最適化を実行することができることを、当業者であれば理解されたい。]
[0030] いくつかの実施形態において、命令をカウントし、所定の数の操作に到達したとき、量子境界を確立することによって、マルチスレッドアプリケーションは、量子に分割される。いくつかの実施形態において、スレッドは通常同じレートで進まないという事実を考慮に入れ、それによってマルチスレッドアプリケーションの実行のクリティカルパスにおけるスレッドの進行を向上させるために、適応量子構築技術が使用される。すなわち、各スレッドは、異なる、しかし決定論的な量子境界を有し得る。図１６は、１つまたは複数の実施形態における、ファシリティによって実行される適応量子プロセス１６００を示すフロー図である。いくつかの実施形態において、トークンを保持するスレッドが予め定義された有限数のメモリ操作を有する量子を実行する間、プロセス１６００がファシリティによって実行される。ステップ１６０５〜１６３５で、ファシリティは、量子の各メモリ操作をループして、量子境界を適応させるかどうかを決定し、それによってマルチスレッドアプリケーションの実行のクリティカルパスの性能を向上させる。ステップ１６０５で、ファシリティは、量子のメモリ操作を選択する。] 図１６
[0031] ステップ１６１０で、ファシリティは、マルチスレッドアプリケーションのクリティカルパスに関連するアプリケーションレベルの同期情報を評価する。いくつかの実施形態において、ファシリティは、別のスレッドがクリティカルパススレッドでありそうかどうかを決定するために、アプリケーションレベルの同期情報を評価する。例えば、こうした情報は、選択されたメモリ操作によって、トークンを保持するスレッドがアプリケーションレベルのロックの解除をもたらすかどうかの指示を含み得る。基本原理は、トークンを保持するスレッドがアプリケーションレベルのロックを解除するとき、他のスレッドは、そのロックを待ちながらスピンしている場合があるということである。別の例として、こうした情報は、別のスレッドがアプリケーションレベルのロック時にスピンを開始したかどうかの指示を含み得る。ファシリティは、待機中のスレッドが前進できるように、できるだけ早くトークンを前方に進めるべきであるかどうかを決定するために、アプリケーションレベル同期情報を評価する。いくつかの実施形態において、スレッドがアプリケーションレベルのロックを解除したとき、またはアプリケーションレベルのロック時にスピンを開始したときに、ファシリティに通知するためのＤＭＰコンポーネントへのコールバックを挿入するために、コンパイラまたはバイナリ書き換えツールが使用される。いくつかの実施形態において、ハードウェアは、アプリケーションレベル同期情報の変化を監視するために使用される。例えば、通常、ロックを実施するために、特殊命令（例えば、ロックプレフィックス命令、ロードリンク／格納条件、ｔｅｓｔ／ｔｅｓｔ＆ｓｅｔ命令など）が使用される。別の例として、ハードウェアは、ロックが解放されている／取得されているときを示すためにソフトウェアが使用する特殊命令を提供することができる。]
[0032] ステップ１６１５で、ファシリティは、共有メモリ情報を評価する。いくつかの実施形態において、ファシリティは、トークンを次のスレッドに進めることができるように、トークンを保持するスレッドが共有データにおける作業を潜在的に終了したかどうかを決定するために、共有メモリ情報を評価する。例えば、こうした情報は、トークンを保持するスレッドが共有メモリにメモリ操作を発行していない予め定められた閾値が経過した（例えば、期間、命令数など）かどうかの指示を含み得る。基本原理は、トークンを保持するスレッドが共有データ上で作業しているとき、他のスレッドがそのデータにすぐにアクセスすることが予測されることである。量子を早く終了させ、トークンを渡すことによって、量子を終了させた場合より早く別のスレッドがデータを消費する可能性がある。いくつかの実施形態において、予め定められた閾値は、例えば３０のメモリ操作など、有限数の動作として測定される。いくつかの実施形態において、ファシリティは、共有メモリデータ構造を使用して、トークンを保持するスレッドによって共有メモリになされるアクセス数を追跡し、次いでその数を１つまたは複数の予め定義された閾値と比較する。いくつかの実施形態において、ファシリティは、予め定義された閾値が経過すると、ファシリティに通知する共有メモリモニタを実装する。]
[0033] ステップ１６２０で、ステップ１６１０〜１６１５で評価された情報に基づいて別のスレッドがクリティカルパススレッドでありそうだとファシリティが決定した場合、ファシリティはステップ１６２５に進み、そうでない場合、ファシリティはステップ１６３５に進む。ステップ１６３５で、量子内の追加のメモリ操作が残っている場合、ファシリティは折り返してステップ１６０５に戻り、そうでない場合、プロセス１６００は終了する。]
[0034] ステップ１６２５で、ファシリティは、元の量子境界に到達することなく量子を終了させる。いくつかの状況下で、量子境界を終了させるためのファシリティの決定は、量子の最後の操作（すなわち、元の量子境界）と実質的に同時に起こり得ることに留意されたい。すなわち、ステップ１６２０で、別のスレッドがクリティカルスレッドでありそうで、量子内にメモリ操作が残っていないことをファシリティが決定した場合、ファシリティは、実際に、ステップ１６２５で、元の量子境界で量子を終了させることができる。]
[0035] ステップ１６３０で、ファシリティは、決定論的順序に従ってトークンを次のスレッドに進め、次いでプロセス１６００が終了する。いくつかの実施形態において、量子を終了させる前に、ファシリティは、トークンを保持するスレッドに、スレッド間通信が行われる新しい量子境界の端部でメモリフェンスを実行させるバリア命令を発行する。メモリフェンスは、バリア命令の前後に発行されるメモリ操作における順序制約をプロセッサに実施させる命令である。バリア命令を発行することによって、ファシリティは、トークンが次のスレッドに進められる前にトークンを保持するスレッドによって実行されるすべてのメモリ操作が終了することを保証する。その結果、メモリに対してトークンを保持するスレッドによってもたらされるメモリに対する変更は、マルチスレッドアプリケーションのスレッドのすべてに対して可視になる。特定のスレッドがアプリケーションレベルのロック時にスピンを開始するという情報の結果、ファシリティが量子を終了させる場合でさえ、ファシリティは、決定論的順序で次のスレッドに対応しない限り、トークンをそのスレッドに進めないことに留意されたい。]
[0036] 量子を終了させるかどうかを決定するためにファシリティによって評価された情報は、トークンを保持するスレッド、選択されたメモリ操作、ＤＭＰおよび／またはアプリケーションレベル同期情報、共有メモリ情報などに関連する他のタイプの情報を含み得ることを、当業者であれば理解されたい。例えば、いくつかの実施形態において、選択されたメモリ操作が共有メモリを介したスレッド間通信を含まないシステムコールであるとき、ファシリティは、量子を終了させ、システムコール前にトークンを次のスレッドに進める。基本原理は、システムコールは、通常、終了に長い時間がかかり、トークンを必要としない場合があることである。その結果、量子を終了させ、システムコールが呼び出される前にトークンを次のスレッドに進めることによって、ファシリティは、量子を終了させた場合より早く進める機会を別のスレッドに提供する。]
[0037] いくつかの実施形態において、ファシリティは、単一スレッドに対して証明可能にローカルなロケーション、および／または単一の量子内でエイリアスでなければならないメモリロケーションにアクセスするメモリ操作を識別することによって、並行性を回復し、共有メモリデータ構造へのアクセスに伴うオーバーヘッドを低減する。図１７は、１つまたは複数の実施形態において共有メモリデータ構造へのアクセスに伴うオーバーヘッドを低減するためにファシリティによって実行されるプロセス１７００のフロー図である。ステップ１７０５で、ファシリティは、マルチスレッドアプリケーションのコードを取得し、次いでステップ１７１０に進む。例えば、これは、マルチスレッドアプリケーションコードのバイナリ形式をソースファイルから読み取ることを含み得る。別の例として、これは、マルチスレッドアプリケーションのバイナリ形式を、制御フローグラフなど、中間形式に変換するコンパイラまたはバイナリ書き換えツールを含み得る。制御フローグラフは、グラフのノードとして動作を指定するプログラム実行の表現である。] 図１７
[0038] ステップ１７１０で、ファシリティは、マルチスレッドアプリケーションの単一スレッドに対してローカル（すなわち、コード生成中「証明可能にローカル」）となることが保証されるマルチスレッドアプリケーションのメモリ操作を識別し、次いでファシリティは、ステップ１７１５に進む。いくつかの実施形態において、ファシリティは、エスケープ分析を使用して、証明可能なローカルデータにアクセスするメモリ操作を識別する。データがある関数で割り当てられ、その関数がポインタをそのデータに戻すと、データは、実行の他のスレッドまたは呼び出し側関数に「逃れる」と言われる。また、データがグローバル変数、または他のデータ構造に格納されており、これらが現在の関数またはスレッドの実行を逃れるものである場合、データも逃れる可能性がある。]
[0039] ステップ１７１５〜１７４０で、ファシリティは、マルチスレッドアプリケーションコードの各量子をループする。ステップ１７１５で、ファシリティは、量子を選択し、次いでステップ１７２０に進む。ステップ１７２０で、ファシリティは、選択された量子点内の２つ以上のメモリ操作が同じメモリロケーションを指す（すなわちメモリ操作同士が「エイリアスでなければならない」）と決定した場合、ステップ１７２５に進み、そうでない場合、ステップ１７４０に進む。例えば、基礎のアドレスおよびオフセットが同じである場合、メモリ操作は、エイリアスでなければならない。ステップ１７２５〜１７３５で、ファシリティは、選択された量子内でエイリアスでなければならないメモリ操作の各グループをループする。ステップ１７２５で、ファシリティは、選択された量子内でエイリアスでなければならないメモリ操作のグループを選択し、次いでステップ１７３０に進む。ステップ１７３０で、ファシリティは、第１のメモリ操作とエイリアスでなければならない選択された量子内の第１のメモリ以降の各メモリ操作を識別し、次いでファシリティは、ステップ１７３５に進む。ステップ１７３５で、追加のグループが残っている場合、ファシリティは折り返してステップ１７２５に戻り、そうでない場合、ファシリティはステップ１７４０に進む。ステップ１７４０で、追加の量子が残っている場合、ファシリティは折り返してステップ１７１５に戻り、そうでない場合、ファシリティはステップ１７４５に進む。ステップ１７４５で、ファシリティは、ステップ１７１０（すなわち、証明可能にローカルなデータにアクセスするメモリ操作）および／または１７３０（すなわち、同じ量子内のより前のメモリ操作に対してエイリアスでなければならない量子内のメモリ操作）で識別されたメモリ操作以外のメモリ操作を追跡するためにコードを挿入し、次いでプロセス１７００が終了する。量子当たりのデータ項目当たり共有メモリデータ構造に一度アクセスすることによって、およびその証明可能にローカルなデータにアクセスするために、スレッドがトークンを保持することを必要としないことによって、ファシリティは、並行性を回復し、共有メモリデータ構造のチェックに伴うオーバーヘッドを低減する。]
[0040] いくつかの実施形態において、ファシリティは、単一のスレッドに対してローカルであるメモリ操作を識別するために実行するとき、マルチスレッドアプリケーションをプロファイルするためのバイナリ書き換えツールを含む。例えば、バイナリ書き換えツールは、共有メモリデータ構造の状態を監視するために実行可能なアプリケーションを取り付けることによってマルチスレッドアプリケーションをプロファイルすることができる。マルチスレッドアプリケーションの実行中に単一のスレッドによってアクセスされるメモリロケーションは、ローカルとして識別され得る。複数の実行にわたってプロファイリング情報が安定しているとき、スレッドがトークンを保持する必要なく、識別されたメモリ操作が実行され得る。しかし、プロファイリングパスがマルチスレッドアプリケーションの特定の実行を反映するため、この技術は完全な決定論を提供しない場合があることに留意されたい。]
[0041] いくつかの実施形態において、ファシリティは、本明細書では「スレッドデータ構造」と呼ばれるＤＭＰデータ構造を含み、その詳細は、図６を参照して以下で説明する。しかし、任意の数のＤＭＰデータ構造が含まれていてよいことに留意されたい。スレッドデータ構造が複数のＤＭＰデータ構造を表し得ることにさらに留意されたい。いくつかの実施形態において、スレッドデータ構造は、実行中にマルチスレッドアプリケーションによって作成される各スレッドに対応するスレッド識別子（「ＩＤ」）を格納する。例えば、スレッドデータ構造は、配列、リンクリスト、キュー、またはスレッドＩＤの他のデータ構造（本明細書では「スレッドコンテナ」と呼ばれる）を含み得る。] 図６
[0042] いくつかの実施形態において、スレッドデータ構造は、量子の実行の順序を制御するために使用され得るトークンを含む。例えば、いくつかの実施形態において、量子を実行する前に、スレッドは、トークンの現在の値がスレッドのＩＤに一致するかどうかを決定する。スレッドのＩＤがトークンの現在の値に一致するとき、スレッドは、量子を実行することができる。そうでない場合、スレッドは、トークンの現在の値がその識別子に一致するまで、量子を実行するのを待つ。]
[0043] いくつかの実施形態において、スレッドが作成される順序は、スレッドが決定論的に実行される順序に対応する。例えば、各スレッドが作成されるとき、スレッドの対応するスレッドＩＤは、スレッドコンテナ内に順次格納され得る（例えば、最初に作成されたスレッドのスレッドＩＤは１、２番目に作成されたスレッドのスレッドＩＤは２など）。操作が実行されるとき、スレッドは、（第１のスレッドＩＤから開始して）スレッドＩＤが格納される順序に基づいてスレッドコンテナに格納されるスレッドＩＤを順次ループすることによって、トークンの値を進めるよう動作するいくつかのＤＭＰ関数を呼び出すことができる。スレッドが存在するとき、通常、スレッドの対応するＩＤがスレッドコンテナから削除されることに留意されたい。]
[0044] いくつかの実施形態において、スレッドデータ構造は、トークンが進められる前にスレッドＩＤがトークンの現在の値に一致するスレッドによって実行され得る決定論的な有限数の（すなわち量子）制御された操作またはブロックに対応する値を格納する。制御された操作またはブロックのこの数は、本明細書では「コミットブロックサイズ」と呼ばれる。コミットブロックサイズは、１つからＮ個までの制御された操作またはブロックに及び得る。大きいコミットブロックサイズおよび小さいコミットブロックサイズには性能のトレードオフが関連することを、当業者であれば理解されたい。例えば、コミットブロックサイズが小さすぎるとき、スレッド間でのコンテキストの切り替えに伴うオーバーヘッドの結果として、マルチスレッドアプリケーションの性能が悪化する。別の例として、コミットブロックサイズが大きすぎるとき、多くのまたはすべてのスレッドは、スレッドＩＤがトークンに一致するスレッド（およびスレッドＩＤがそのスレッドＩＤに先行するすべてのスレッド）がコミットブロックサイズによって指定された数の制御された操作を終了する、または実際に実行するのを待つのを余儀なくされ得るため、マルチスレッドアプリケーションの性能が悪化する。少なくとも１つの実施形態において、コミットブロックサイズは、１，０００に等しい。]
[0045] いくつかの実施形態において、コミットブロックサイズは、構成可能である。例えば、コミットブロックサイズは、マルチスレッドアプリケーションの様々なスレッドインターリービングをプログラム的に操作し、テストするように、ソフトウェア開発者によって構成され得る。別の例として、コミットブロックサイズは、マルチスレッドアプリケーションによって作成され得る最大数のスレッド、および／またはマルチスレッドアプリケーションが実行するマルチプロセッシングシステムのプロセッサまたはコアの数に基づいて、自動的に構成され得る。スレッドによって実行される制御された操作の数をカウントするために様々な技術が使用され得ることを、当業者であれば理解されたい。例えば、いくつかの実施形態において、スレッドデータ構造は、スレッドＩＤが現在のトークンＩＤに一致するスレッドによって実行された制御された操作の数に対応する値を含む。スレッドが制御された操作を実行するたびに、制御された操作の数は、増分され、コミットブロックサイズと比較される。制御された操作の数がコミットブロックサイズに等しい場合、トークンは、次のスレッドＩＤに進められ、制御された操作の数は、ゼロにリセットされる。]
[0046] マルチスレッドアプリケーションを増補して、いくつかのスレッドの操作（例えば、制御されたスレッド操作）の順序を制御することによって、開発プロセスは、かなり簡略化される。例えば、ファシリティは、マルチスレッドアプリケーションのスレッドインターリービングを直接操作し、それによってマルチスレッドアプリケーションの実質的により良いテストカバレージを可能にできるようにするために、ソフトウェア開発者によって使用され得る。開発者は、例えばコミットブロックサイズを変更することによって、制御されたスレッド操作のインターリービングを操作することができる。別の例として、開発者は、スレッドが実行する決定論的順序を変更することによって、制御されたスレッド操作のインターリービングを操作することができる。いくつかの実施形態において、ファシリティによって、ソフトウェア開発者は、挿入されたコードが量子構築物に影響を与えないように、増補のために挿入されたとコードをマーク付けすることができる。]
[0047] いくつかの実施形態において、ファシリティは、ソフトウェア開発者がテストのためにそのアプリケーションをサブミットすることができるバグファインダウェブサービスを提供する。図２３は、いくつかの実施形態における、バグファインダウェブサービス２３００を示す高レベルデータフロー図である。示された実施形態において、バグファインダウェブサービス２３００は、インターネットまたはローカルエリアネットワークなどのネットワーク２３１０を介してコンピュータ２３０５を使用してソフトウェア開発者からの要求を受信する。いくつかの実施形態において、要求は、テストされるマルチスレッドアプリケーション２３１５のコピーを含む。例えば、要求は、マルチスレッドアプリケーションバイナリを含み得る。別の例として、要求は、マルチスレッドアプリケーションのソースコードを含み得る。いくつかの実施形態において、要求は、マルチスレッドアプリケーション２３１５のコピーが取り出され得るロケーションの指示を含む。いくつかの実施形態において、要求は、アプリケーションがテストされるテストスイート２３２０を含む。] 図２３
[0048] いくつかの実施形態において、マルチスレッドアプリケーション２３１５をテストする旨の要求の受信に応答して、バグファインダウェブサービス２３００は、マルチプロセッシングシステム２３２５に要求をディスパッチする。マルチプロセッシングシステム２３２５は、テスト中のマルチスレッドアプリケーション（ＭＵＴ）２３３５の実行を決定論的に制御するため、およびＭＵＴ２３３５の様々なスレッドインターリービングをプログラム的にテストするために使用されるＤＭＰシステム５００など、決定論的マルチプロセッシング（ＤＭＰ）システム２３２０を含む。いくつかの実施形態において、マルチプロセッシングシステム２３２５は、ＭＵＴ２３３５をテストするために使用されるテストスイート２３４０を含む。例えば、テストスイート２３４０は、１つまたは複数の入力および予想される対応する出力を含み得る。別の例として、テストスイート２３４０は、ＭＵＴ２３２５とのユーザ対話をシミュレートする１つまたは複数の自動スクリプトを含み得る。いくつかの実施形態において、ＭＵＴ２３３５は、マルチプロセッシングシステム２３２５において直接実行される。いくつかの実施形態において、ＭＵＴ２３３５は、マルチプロセッシングシステムにおいて実行する仮想マシン内で実行される。]
[0049] いくつかの実施形態において、マルチプロセッシングシステム２３２５は、バグロギングコンポーネント２３４５を含む。バグロギングコンポーネント２３４５は、いつＭＵＴ２３３５が指定された入力について誤った出力を生成するか、および／またはＭＵＴ２３３５がクラッシュするかを観察することができる。ＭＵＴ２３３５が誤った出力を生成する、またはクラッシュするとき、バグロギングコンポーネント２３４５は、誤った出力またはクラッシュを生成したバグのソースを決定する（例えば、特定の決定論的スレッド順序の１つまたは複数の共有メモリアクセス）。次いでバグロギングコンポーネント２３４５は、バグログにおけるバグの決定されたソースを格納する。いくつかの実施形態において、バグログは、データストア２３５０に格納される。データストア２３５０は、ＭＵＴ２３３５のコピーまたはＭＵＴ２３３５のコピーが配置され得るロケーションの指示を含み得る（例えば、ＭＵＴ２３３５がテストされたマルチプロセッシングシステム２３２５）。データストア２３５０は、テストスイート２３４０またはテストスイート２３４０が配置され得るロケーションの指示を含み得る。データストア２３５０は、ＭＵＴ２３３５のソフトウェア開発者またはベンダーに関連付けられたアカウント情報など、他の情報を含み得る。]
[0050] いくつかの実施形態において、バグファインダウェブサービス２３００は、無料サービスとして提供される。すなわち、バグファインダウェブサービス２３００は、ソフトウェア開発者に負担をかけることなく、マルチスレッドアプリケーション２３１５をテストする。いくつかの実施形態において、バグファインダウェブサービス２３００は、時給ベースの加入に基づいて、またはテストサイクル当たりの請求と引き換えに、マルチスレッドアプリケーション２３１５をテストする。]
[0051] いくつかの実施形態において、バグファインダウェブサービス２３００は、以下のビジネスモデルに従って動作する。それは、テスト結果を示すソフトウェア開発者にメッセージを送信する。ＭＵＴ２３３５においてバグが識別されないとき、バグファインダウェブサービス２３００は、バグがＭＵＴ２３３５で識別されなかったことを示すメッセージをソフトウェア開発者に送信する。バグが識別されると、バグファインダウェブサービス２３００は、バグが識別されたことを示すメッセージをソフトウェア開発者に送信する。いくつかの実施形態において、メッセージは、有料でソフトウェア開発者にバグの識別を販売するという申し出を含む。例えば、料金は、識別されたバグの数に基づく、均一料金とする、などでもよい。ソフトウェア開発者が申し出を受け入れた場合、バグファインダウェブサービスは、ソフトウェア開発者に識別されたバグのそれぞれを明らかにする。例えば、識別されたバグ結果は、ウェブページにおいてソフトウェア開発者に表示され得る。別の例として、識別されたバグ結果は、メッセージでソフトウェア開発者に送信され得る。いくつかの実施形態において、識別されたバグごとに、結果は、入力の指示、誤った出力またはＭＵＴ２３３５がクラッシュしたことの指示、識別されたバグを生成した１つまたは複数の共有メモリアクセス、識別されたバグを生成したスレッド順序、量子サイズなどを含む。いくつかの実施形態において、メッセージは、ソフトウェア開発者のコンピュータ２３０５において識別されたバグを再生するための機構を含む。例えば、メッセージは、スレッドが実行する順序、およびバグを識別するために使用されるパラメータ（例えば、量子サイズおよび／またはスレッド順序）を制御するために取り付けられるバイナリアプリケーションを含み得る。いくつかの実施形態において、メッセージは、マルチスレッドアプリケーション２３１５を配置した顧客によって報告されたバグが回避され得るように、識別されたバグの１つまたは複数を中央バグライブラリに報告するためのオプションを含む。バグの回避については、本明細書において、図１８〜２０との関連でさらに説明される。] 図１８ 図１９ 図２０
[0052] 様々な実施形態は、上述した環境に関して説明されるが、バグファインダウェブサービス２３００は、単一のモノリシックコンピュータシステム、および様々な方法で接続されたコンピュータシステムまたは類似の装置の他の様々な組み合わせを含めて、様々な他の環境に実装され得ることを当業者であれば理解されたい。]
[0053] 図２４は、いくつかの実施形態における、ファシリティによって実行されるバグファインダプロセス２４００のフロー図である。示されたバグファインダプロセス２４００は、バグが識別されない限り、ソフトウェア開発者にとって無料であり、ソフトウェア開発者は、識別されたバグを明らかにさせるために料金を支払うことを選択する。ステップ２４０５において、ファシリティは、マルチスレッドアプリケーションなど、アプリケーションをテストする旨のバグファインダ要求を受信する。例えば、要求は、インターネットなど、ネットワークを介してソフトウェア開発者から受信され得る。要求は、マルチスレッドアプリケーションバイナリおよび／またはマルチスレッドアプリケーションがテストされるテストスイートを含み得る。ステップ２４１０で、ファシリティは、マルチスレッドアプリケーションの様々なスレッドインターリービングをプログラム的にテストする。例えば、ファシリティは、テストスイートに含まれる入力および／またはスクリプトを使用してマルチスレッドアプリケーションをテストすることができる。マルチスレッドアプリケーションの実行パスごとに、ファシリティは、量子サイズおよび／またはスレッド実行順序を変更して、マルチスレッドアプリケーションの複数のスレッドインターリービングをプログラム的にテストすることができる。ステップ２４１５で、任意のバグが識別された場合、ファシリティはステップ２４２５に進み、そうでない場合、ファシリティはステップ２４２０に進む。ステップ２４２０で、ファシリティは、バグが識別されなかったことを示すメッセージを送信し、次いでプロセス２４００は終了する。ステップ２４２５で、ファシリティは、無料でソフトウェア開発者に識別されたバグを明らかにすることを申し出るメッセージを送信する。ステップ２４３０で、申し出が受け入れられた場合、ファシリティはステップ２４３５に進み、そうでない場合、ファシリティは折り返してステップ２４３０に戻る。いくつかの実施形態において、ファシリティは、ソフトウェア開発者によって後で取り出すために、識別されたバグを格納する。例えば、ソフトウェア開発者がアカウントを有する場合、ファシリティは、指定された期間の間結果を格納することができる。ステップ２４３５で、ファシリティは、ソフトウェア開発者に識別されたバグのそれぞれを明らかにする。次いでプロセス２４００が終了する。様々な実施形態において、ファシリティは、ステップ２４１０に関連して示され、説明されたテストに加えて、またはその代わりに、他の様々な種類のテストを実行する。] 図２４
[0054] いくつかの実施形態において、マルチスレッドアプリケーションは、その増補された形で配置される。マルチスレッドアプリケーションを増補された形で配置することによって、アプリケーションの信頼性は、実質的に向上する。というのは、例えば、「現場での」（すなわち顧客による）マルチスレッドアプリケーションの実行は、社内でのアプリケーションのテストに、より似たものになるからである。さらに、マルチスレッドアプリケーションがクラッシュする、または同期バグを経験するとしたら、ソフトウェア開発者は、顧客から意味のあるクラッシュ情報を集めることによって欠陥を迅速に解決することができる。すなわち、増補された形で配置されると、クラッシュに先行する顧客によって実行されるアクションは、ソフトウェア開発者がクラッシュを容易に再生することができるようになるため、意味がある。その結果、ソフトウェア開発者は、クラッシュまたは同期バグがスレッドの未知のインターリービングに関連付けられた場合より実質的に早く欠陥を解決することができる。したがって、ファシリティは、マルチスレッドアプリケーションの開発および配置の両方を向上させる。]
[0055] いくつかの実施形態において、ファシリティは、仮想マシンモニタ（ＶＭＭ）を含むマルチプロセッシングシステムに実装される。ＶＭＭは、マルチプロセッシングシステムなど、物理的なコンピューティングシステムのリソースを仮想化して、オペレーティングシステムおよび／または任意の数のアプリケーションが実行される仮想マシンを提供するソフトウェアレイヤである。本明細書で使用されるとき、仮想マシン（ＶＭ）は、ＶＭＭを介して実装されるマルチプロセッシングシステムの論理的な例である。図１８は、１つまたは複数の実施形態における、仮想マシン内のマルチスレッドアプリケーションのスレッドの実行を決定論的に制御するために決定論的マルチプロセッシング（ＤＭＰ）システムと共に実行するＶＭＭを示す高レベルブロック図である。説明を曖昧にするのを回避するために、いくつかのよく知られている構造および機能は、詳細に示されても述べられてもいない。いくつかの実施形態において、仮想マシンモニタ（ＶＭＭ）１８００は、図４との関連で説明されるコンピューティングシステム４００など、マルチプロセッシングシステムに実装される。ＶＭＭ１８００は、仮想マシン（ＶＭ）１８０５に、それぞれＶＭＭ１８００が実行する物理リソースの仮想インスタンスを表す仮想プロセッサ１８１０ａ〜１８１０ｎ、仮想メモリ１８１５、仮想ドライバ１８２０などを含む仮想化された１組のリソースへのアクセスを提供する。ＶＭ１８０５は、マルチスレッドアプリケーション１８２５など、１つまたは複数のアプリケーションも含み得る。ＶＭＭ１８００は任意の数の仮想マシンを含み得ることに留意されたい。いくつかの実施形態において、ＶＭＭ１８００は、「ホスト型」ＶＭＭであり、これは、マルチプロセッシングシステムにおける他のアプリケーションと同様に扱われ、他のアプリケーションとシステムリソースの使用を共有することを意味する。一方、他の実施形態では、ＶＭＭ１８００は、「非ホスト型」ＶＭＭであり、これは、ＶＭＭは、オペレーティングシステムのサポートなく、システムリソースに直接アクセスすることを意味する。] 図１８ 図４
[0056] いくつかの実施形態おいて、ＶＭＭ１８００は、マルチスレッドアプリケーション１８２５を決定論的順序で実行される量子に分割する決定論的マルチプロセッシング（ＤＭＰ）システム１８３０を含む。マルチスレッドアプリケーション１８２５のスレッドによって量子が実行される順序を制御することによって、ＤＭＰシステム１８３０は、マルチスレッドアプリケーションが決定論的に挙動できるようにする。いくつかの実施形態において、ＤＭＰシステム１８３０は、オペレーティングシステム（図示せず）が決定論的に挙動できるようにする。しかし、ＤＭＰシステム１８３０はＶＭＭ１８００によって実装される必要がないことに留意されたい。例えば、いくつかの実施形態において、ＤＭＰシステム１８３０は、ＶＭＭ１８００の外部に、またはマルチスレッドアプリケーション１８２５が入力として提供される個別のコンピューティングシステムによって実装される。]
[0057] いくつかの実施形態において、ＶＭＭ１８００は、アプリケーションのクラッシュを観察し、バギーシーケンス（buggy sequence）（例えば、最終的にアプリケーションにクラッシュさせるメモリアクセスに先行する特定の決定論的スレッド順序のための１つまたは複数の共有メモリアクセス）を決定し、決定されたバギーシーケンスをバグライブラリ１８４０に格納するバグ報告コンポーネント１８４５を含む。]
[0058] いくつかの実施形態において、ＶＭＭ１８００は、スレッド間通信を監視して、既知のバギーシーケンスを検出し、回避するスレッド通信モニタ１８３５を含む。スレッド通信モニタ１８３５は、スレッドが共有メモリにアクセスする順序を観察し、その順序を、バギーであることがわかっている（すなわち、最終的にアプリケーションにクラッシュさせる）シーケンスと一致させることによって、バギーシーケンスを検出することができる。「バギーシーケンス」は、最終的にアプリケーションにクラッシュさせるインターリービングに先行する１つまたは複数のインターリービングパターン（例えば、特定の決定論的順序のための共有メモリアクセス）を含み得る。スレッド通信モニタ１８３５は、バギーシーケンスが検出されるとき、有効なインターリービングを選択することによってアプリケーションにクラッシュさせる既知のバギーシーケンスを回避することができる。これは、例えば、量子サイズまたはスレッドが実行される決定論的順序への変更をトリガすることによって達成され得る。]
[0059] 図１９は、１つまたは複数の実施形態における、ファシリティによって実行される監視プロセス１９００のフロー図である。例えば、監視プロセス１９００は、マルチスレッドアプリケーションがマルチプロセッシングシステム上において、仮想マシン内で実行する間に実行され得る。いくつかの実施形態において、監視プロセス１９００は、スレッド通信モニタ１８３５によって実行される。マルチスレッドアプリケーションが実行する間に、ファシリティは、ステップ１９０５〜１９１５をループする。ステップ１９０５で、ファシリティは、共有メモリへのスレッドのアクセスを観察する。例えば、ファシリティは、１つまたは複数の指定されたメモリロケーションへのアクセスを観察し、アクセスパターンがバギーであることがわかっているインターリービングシーケンスのパターンに対応するかどうかを決定することができる。別の例として、ファシリティは、Ｎ個のアクセスを観察することができ、ここでは、Ｎは、量子当たりの平均メモリアクセス数×量子数に等しい。Ｎ個の観察されたアクセス数はアプリケーション間で変わり得ることに留意されたい。したがって、特定の数への言及は、制限とみなされるべきではない。非常に多くの、または非常に少ない観察されたアクセス数を確立することには性能のトレードオフが関連することを、当業者であれば理解されたい。例えば、観察されたアクセス数が少なすぎるとき、ファシリティは、シーケンス内のインターリービングを、それがそうでなくてもバギーとして検出する場合がある。別の例として、観察されたアクセス数が多すぎるとき、ファシリティは、アプリケーションがクラッシュする前に、バギーシーケンスを検出できない場合がある。] 図１９
[0060] ステップ１９１０で、観察されたアクセスがバギーシーケンスに一致することをファシリティが決定した場合、ファシリティはステップ１９１５に進み、そうでない場合、ファシリティは折り返してステップ１９０５に戻る。ステップ１９１５で、次の量子境界で、ファシリティは、スレッドインターリービングを変更し、次いで、折り返してステップ１９０５に戻る。例えば、ファシリティは、スレッドが実行される決定論的順序を変更することができる。別の例として、ファシリティは、量子サイズを変更することができる。いくつかの実施形態において、ファシリティは、観察されたアクセスがバギーシーケンスに一致したことを決定したとき、スレッドインターリービングを変更する。すなわち、いくつかの実施形態において、ファシリティは、次の量子境界に到達するのを待たない。マルチスレッドアプリケーションが、１８００など、並行処理のバグの動的な回避を提供するＶＭベースのマルチプロセッシングシステム内に配置されると、マルチスレッドアプリケーションの信頼性は、実質的に向上する。というのは、ユーザは、アプリケーションのベンダーが並行処理のバグを修正するのにかかる時間の間、保護されるからである。]
[0061] いくつかの実施形態において、バグ報告コンポーネント１８４５は、アプリケーションがクラッシュすると、バグライブラリ１８４０を更新する。いくつかの実施形態において、バグ報告コンポーネント１８４５は、バグアグリゲータサービスからバグ更新を受信し、または取り出すことによって、バグライブラリ１８４０を更新する。]
[0062] 図２０は、１つまたは複数の実施形態における、バグアグリゲータサービス２０００を示す高レベルデータフロー図である。いくつかの実施形態において、バグアグリゲータサービス２０００は、１つまたは複数のアプリケーションに関連付けられたバグを集める。バグアグリゲータサービス２０００は、マルチスレッドアプリケーションおよび／または単一スレッドアプリケーションに関連付けられたバグを集めることができることに留意されたい。したがって、マルチスレッドアプリケーションへの言及は、制限とみなされるべきではない。] 図２０
[0063] 図２０において、バグアグリゲータサービス２０００は、インターネットまたはローカルエリアネットワークなどのネットワーク２０１５を介して、いくつかのマルチプロセッシングシステム２０１０ａ・・・２０１０ｚに、マルチスレッドアプリケーション２００５に関連付けられたバギーシーケンスを送信し、そこからバギーシーケンスを受信する。示された実施形態において、各マルチプロセッシングシステム２０１０は、マルチスレッドアプリケーション２００５が決定論的に挙動し、スレッド通信モニタ２０２５がバギーシーケンスを検出し、回避することができるようにするためのＤＭＰシステム２０２０を含む。スレッド通信モニタ２０２５によってアクセスされるバギーシーケンスは、マルチプロセッシングシステム２０１０にあるバグライブラリ２０３０内にローカルに格納され、および／またはバグアグリゲータサービス２０００によって維持される中央バグライブラリ２０３５内にリモートに格納され得る。示された実施形態において、各マルチプロセッシングシステム２０１０は、マルチスレッドアプリケーション２００５がいつクラッシュするかを観察し、クラッシュを生成するバギーシーケンス（例えば、最終的にマルチスレッドアプリケーション２００５にクラッシュさせた共有メモリアクセスに先行する特定の決定論的スレッド順序のための１つまたは複数の共有メモリアクセス）を決定し、決定されたバギーシーケンスを格納するためのバグ報告コンポーネント２０４０をさらに含む。バグ報告コンポーネント２０４０は、それが動作するマルチプロセッシングシステム２０１０のバグライブラリ２０３０、別のマルチプロセッシング装置のバグライブラリ２０３０、および／または中央バグライブラリ２０３５への更新を格納することができる。中央バグライブラリ２０３５への更新は、バグアグリゲータサービス２０００に送信され、および／またはネットワーク２０１５を介して中央バグライブラリ２０３５に直接送信され得る。マルチプロセッシングシステム２０１０の中央バグライブラリ２０３５またはバグライブラリ２０３０への更新は、単発で、定期的に、低アクティビティの期間中などに行われ得る。いくつかの実施形態において、マルチプロセッシングデバイス２０１０のバグライブラリ２０３０への更新は、マルチプロセッシングシステム２０１０によって実行されるマルチスレッドアプリケーション２００５に関連付けられたバグに限定される。一方、他の実施形態では、更新が送信され、および／または受信されるマルチスレッドアプリケーション２００５を選択するためにユーザインターフェイスが設けられる。] 図２０
[0064] 様々な実施形態は、上述した環境に関して記載されるが、バグ情報の集まりおよび／または分配は、単一のモノリシックコンピュータシステム、および様々な方法で接続されたコンピュータシステムまたは類似の装置の他の様々な組み合わせを含めて、様々な他の環境に実装され得ることを当業者であれば理解されたい。例えば、様々な実施形態において、マルチプロセッシングシステム２０１０は、バグ情報を集め、および／または共有するために、ＤＭＰシステム、スレッド通信モニタ、およびバグ報告コンポーネントと共に仮想マシンモニタ（図示せず）を実装する。]
[0065] いくつかの実施形態において、マルチスレッドアプリケーションが開発される、および／またはマルチスレッドアプリケーションが配置されるコンピューティングシステムは、共有メモリへのアクセスを制御するためのトランザクショナルメモリ（「ＴＭ」）システムを含む。トランザクショナルメモリシステムは、ハードウェアトランザクショナルメモリ（「ＨＴＭ」）、ソフトウェアトランザクショナルメモリ（「ＳＴＭ」）システム、またはハイブリッドハードウェア−ソフトウェア（ＨＳ−ＴＭ）システムとすることができる。両方のＴＭシステムは、当分野で知られている。ＳＴＭシステムは、プログラミングアブストラクション（programming abstraction）を提供し、それを介して、スレッドは、共有リソースをロックすることなく、または共有リソースが解放されるのを待つことなく、その一部に１つまたは複数の共有リソース（例えばメモリ）が関与し得る操作のシーケンスをアトミック的に実行する。]
[0066] 従来のＴＭシステムは、他のスレッドが何をしているかに関係なく、スレッドが共有メモリへの変更を終了するという点で「楽観的」である。これは、例えば、マルチスレッドアプリケーションのスレッドごとにログを維持することによって達成され、トランザクションごとに、各スレッドは、その対応するログにその操作を順次記録する。例えば、ログは、メモリロケーションの数およびタイプ、並びにトランザクション中にスレッドが読み取り、および／または書き込む値を含み得る。トランザクションの最後に、他のスレッドが同じ共有メモリロケーションに並行してアクセスしなかった場合、スレッドは、実際に、操作のシーケンスを実行する（これは一般に「コミット」と呼ばれる）。しかし、別のスレッドが同じメモリロケーションのうちの１つまたは複数に並行してアクセスした場合、トランザクションは、中止され、再開される。すなわち、従来のＴＭシステムにおいて、同じトランザクション中に共有リソースが複数のスレッドによってアクセスされない限り、トランザクションは、並行して実行する。]
[0067] 従来のＴＭシステムに関連付けられた欠点がいくつかある。例えば、従来のＴＭシステムは、開発者がいくつかの操作、またはいくつかの操作のシーケンスをアトミックとして宣言できるようにすることによって、開発をある程度簡略化するが、従来のＴＭシステムは、マルチスレッドアプリケーションの決定論的マルチプロセッシングを提供しない。さらに、従来のＴＭシステムでは、ソフトウェア開発者は、マルチスレッドアプリケーションにおけるスレッドのインターリービングを指定し、または操作することができない。その結果、従来のＴＭシステムは、潜在的な同期バグにも苦しむ。また、ＨＴＭシステムと比較すると、ＳＴＭシステムは、ログの維持に伴うオーバーヘッド、およびトランザクションのコミットに費やされた時間の結果、パフォーマンスヒットを被る。]
[0068] いくつかの実施形態において、ファシリティは、ＨＴＭ、ＳＴＭ、ＨＳ−ＴＭシステムなど、共有リソースへのアクセスを制御するためにトランザクショナルメモリシステムを使用するマルチスレッドアプリケーションのいくつかのスレッド操作の実行の順序を制御する。すなわち、ファシリティは、スレッドが開始する、および／またはトランザクショナルメモリシステムにおけるトランザクションをコミットする順序を制御することができる。いくつかの実施形態において、ファシリティは、ＳＴＭシステムによって提供されるアプリケーションプログラミングインターフェイス（「ＡＰＩ」）を増補する。一例として、ファシリティは、以下の表１に示されたＳＴＭ ＡＰＩの関数を増補することができる。ファシリティのいくつかの実施形態は、表１に提供されるＳＴＭ ＡＰＩを参照して記載されるが、ファシリティは様々なトランザクショナルメモリシステムにおいて動作し得ることを、当業者であれば理解されたい。]
[0069] ]
[0070] いくつかの実施形態において、ソフトウェア開発者は、マルチスレッドアプリケーション内のアトミックブロックを手動で指定する。例えば、ソフトウェア開発者は、以下のアトミックブロックを含み得る。]
[0071] ]
[0072] コンパイル後、上記のアトミックブロック例は、以下の擬似コードによって置き換えられることになる。]
[0073] ]
[0074] いくつかの実施形態において、トランザクションのうちの１つまたは複数（すなわち、アトミックブロック）は、ソフトウェア開発者に可視ではない。例えば、これらは、コンパイラ、ランタイム、ＴＭシステム、またはその何らかの組み合わせによって挿入され得る。いくつかの実施形態において、ブロックがソフトウェア開発者によって指定されたか、それともコンパイラ、ランタイム、またはＴＭシステムによって挿入されたかにかかわらず、アトミックブロックは、増補される。いくつかの実施形態において、スレッドがＳＴＭＡＰＩの増補された関数を呼び出すと、関数は、トークンの現在の値に対応するスレッドＩＤをチェックするＤＭＰ関数に制御を転送し、これは、トランザクションを開始し、および／または決定論的にコミットするために使用される。多くの異なる技術はトランザクションをインターセプトするために使用され得ることを、当業者であれば理解されたい。例えば、いくつかのＳＴＭ ＡＰＩは、ＡＰＩ関数の実行前および／または後に、制御をＤＭＰ関数に転送するために、フックが登録され得るコールバック機構を提供する。]
[0075] 増補されたトランザクショナルメモリシステムのトランザクションは、サイズが決定論的である。すなわち、各スレッドは、ブロックにおいて特定数の操作（本明細書では「コミットブロックサイズ」と呼ばれる）を実行し、次いでスレッドは、ＩＤがトークンの現在の値に一致するスレッドで開始して、決定論的にコミットしようと試みる。トランザクションが有効であり、スレッドＩＤがトークンに一致する場合、スレッドは、ＳＴＭ＿Ｃｏｍｍｉｔ＿Ｔｒａｎｓａｃｔｉｏｎ（）を呼び出す。トランザクションがコミットされた後、トークンは、次のスレッドＩＤに進められる。しかし、トランザクションが無効である場合（例えば、スレッドがそのトランザクション中に別のスレッドによって書き込まれたロケーションから読み取ったため）、スレッドはＳＴＭ＿Ａｂｏｒｔ＿Ｔｒａｎｓａｃｔｉｏｎ（）を呼び出す。通常、スレッドＩＤがトークンに一致するスレッドがその対応するトランザクションを正常にコミットするまで、トークンは進められないことに留意されたい。]
[0076] いくつかの実施形態において、トークンの現在の値がトランザクションを実行するスレッドのスレッドＩＤに一致しない場合、いくつかのタイプの操作は、トランザクションに即座に中止させる。例えば、トランザクションがＩ／Ｏ操作など元に戻すことができない操作を含むとき、トランザクションを実行するスレッドは、そのスレッドＩＤがトークンに一致するかどうかを決定する。そのスレッドＩＤがトークンに一致する場合、トランザクションは、続行し得る。そうでない場合、トランザクションは、自動的に中止され得る。]
[0077] いくつかの実施形態では、中止されたスレッド以降のスレッドＩＤを有するすべてのスレッドが中止され、一方、別の実施形態では、並行のトランザクションが同じ共有リソースにアクセスしたスレッドのみが中止され、再開される。通常、スレッドＩＤがトークンに一致するスレッドがその対応するトランザクションを正常にコミットするまで、トークンは進められない。その結果、それらのトランザクションを中止しなかった中止されたスレッド以降のスレッドＩＤを有する任意のスレッドは、ＳＴＭ＿Ｃｏｍｍｉｔ＿Ｔｒａｎｓａｃｔｉｏｎ（）を呼び出す前に、トークンがそのスレッドＩＤに一致するのを待つ。]
[0078] 増補された形のＨＴＭを有するコンピューティングシステムにおいてマルチスレッドアプリケーションが実行されると、マルチスレッドアプリケーションは、実質的に性能のペナルティなく、決定論的に実行され得ることに留意されたい。その結果、ソフトウェア開発者および／または製造業者は、スレッドインターリービングの可能性について徹底的にテストしたことを知っているマルチスレッドアプリケーションを配布することができる。したがって、同期バグがマルチスレッドコードに残っている場合でさえ、顧客には見えない。]
[0079] より詳しくファシリティについて説明する前に、ファシリティを実施することができる環境について検討することが有用である。図４は、１つまたは複数の実施形態における、ファシリティが実行するコンピューティングシステム４００のアーキテクチャ例を示す高レベルブロック図である。説明を曖昧にするのを回避するために、いくつかのよく知られている構造および機能は、詳細に示されても述べられてもいない。コンピューティングシステム４００は、相互接続システム４１５に結合された１つまたは複数のプロセッサ４０５およびメモリ４１０を含む。プロセッサ４０５は、コンピューティングシステム４００の中央処理装置（「ＣＰＵ」）であり、したがってその操作全体を制御する。いくつかの実施形態において、プロセッサ４０５は、メモリ４１０に格納されたソフトウェアを実行することによってこれを達成する。いくつかの実施形態において、コンピューティングシステム４００は、単一の集積回路（「ダイ」と呼ばれる）から成るパッケージ、ひとまとめにされた１つまたは複数のダイ、複数のパッケージなどに２つ以上の独立したコアを有するプロセッサ４０５を含む。いくつかの実施形態において、コンピューティングシステム４００は、単一のコアのみを有するにもかかわらず、マルチコアプロセッサとして実行することができるハイパースレッドプロセッサ４０５を含む。プロセッサ４０５は、１つまたは複数のプログラム可能な汎用または専用マイクロプロセッサ、デジタル信号プロセッサ（「ＤＰＳ」）プログラム可能コントローラ、特定用途向け集積回路（「ＡＳＩＣ」）、プログラム可能論理装置（「ＰＬＤ」）など、またはこうした装置の組み合わせとすることができ、またはそれらを含み得る。] 図４
[0080] 図４に示される相互接続システム４１５は、適切なブリッジ、アダプタ、および／またはコントローラによって接続される任意の１つまたは複数の個別の物理バスおよび／またはポイントツーポイント接続を表す抽象概念である。相互接続システム４１５は、例えば、システムバス、ある形の周辺機器コンポーネント相互接続（ＰＣＩ）バス、ハイパートランスポートまたは業界標準アーキテクチャ（ＩＳＡ）バス、小型コンピュータシステムインターフェイス（ＳＣＳＩ）バス、ユニバーサルシリアルバス（ＵＳＢ）、電気電子技術者協会（ＩＥＥＥ）標準１３９４バス（時として「ＦｉｒｅＷｉｒｅ」と呼ばれる）などを含み得る。] 図４
[0081] システムメモリ４１０は、プログラムおよびデータが使用されている間にそれらを格納するためのメモリ４２０、プログラムおよびデータを永続的に格納するためのハードドライブなどの固定記憶装置４２５、およびコンピュータ可読媒体に格納されるプログラムおよびデータを読み取るためのＣＤ−ＲＯＭまたはＤＶＤ−ＲＯＭドライブなどのコンピュータ可読媒体ドライブ４３０を含む。本明細書で使用される場合、システムメモリ４１０は、任意の形の揮発性、不揮発性、取外式、および固定式媒体、またはコンピュータ可読命令、データ構造、プログラムモジュール、およびコンピューティングシステム４００の他のデータなどの情報を格納することができるこうした媒体装置の任意の組み合わせを含む。]
[0082] また、プロセッサ４０５には、相互接続システム４１５を介して、ネットワークアダプタ４３５、１つまたは複数の入力装置および出力装置（「Ｉ／Ｏ装置」）４４０も結合される。ネットワークアダプタ４３５は、コンピューティングシステム４００に、ネットワークを介して他のコンピューティングシステムと通信することができる機能を提供し、例えば、Ｅｔｈｅｒｎｅｔ(登録商標)アダプタとすることができる。Ｉ／Ｏ装置４４０は、コンピューティングシステム４００のユーザに、システムメモリ４１０に格納されるプログラムおよびデータにアクセスすることができる機能を提供する。例えば、Ｉ／Ｏ装置４４０は、キーボード、ポインティング装置、マイクロフォンなどの入力装置、および表示装置、スピーカ、プリンタなどの出力装置を含み得る。上述したように構成されたコンピューティングシステムは、通常、ファシリティの操作をサポートするために使用されるが、様々なタイプおよび構成の装置を使用して、様々なコンポーネントを有するファシリティが実装され得ることを、当業者であれば理解されたい。]
[0083] 図５は、１つまたは複数の実施形態における、決定論的マルチプロセッシングシステム５００の様々な機能的要素を示す高レベルブロック図である。決定論的マルチプロセッシングシステム５００はコンピューティングシステム４００によって実装される必要がないことに留意されたい。例えば、いくつかの実施形態において、決定論的マルチプロセッシングシステム５００は、マルチスレッド型ソフトウェアコードが入力として提供される個別のコンピューティングシステムに実装される。ＤＭＰシステム５００はハードウェア、ソフトウェア、またはハードウェアおよびソフトウェアの組み合わせに実装され得ることにさらに留意されたい。したがって、特定の実装への言及は、制限とみなされるべきではない。] 図５
[0084] いくつかの実施形態において、決定論的マルチプロセッシングシステム５００は、量子ビルダコンポーネント５０５および決定論的マルチプロセッシング（「ＤＭＰ」）コンポーネント５１０を含む。量子ビルダコンポーネント５０５は、例えば、ＤＭＰコンポーネント５１０によって提供される関数５１５〜５４０のうちの１つまたは複数を使用して、マルチスレッドアプリケーション５４５のコードを増補するコンパイラモジュールとして実装され得る。ＤＭＰコンポーネント５１０によって提供される関数は様々な方法で変更され得ることを、当業者であれば理解されたい。例えば、いくつかの関数がマージまたは分割されてもよく、いくつかの関数が省略されてもよく、いくつかの関数が追加されてもよい。いくつかの実施形態において、量子ビルダコンポーネント５０５は、例えば低レベル仮想マシン（「ＬＬＶＭ」）コンパイラインフラストラクチャ内など、コンパイラインフラストラクチャ内にコンパイラパスとして実装される。一方、他の実施形態では、量子ビルダコンポーネント５０５は、マルチスレッドアプリケーションコード５４５が入力として提供される個別のシステムによって実装される。]
[0085] 示された実施形態において、決定論的マルチプロセッシングシステム５００は、マルチスレッドアプリケーションコード５４５を受信し、および／またはそれにアクセスする。マルチスレッドアプリケーションコード５４５は１つまたは複数のコードファイルを表し得ることに留意されたい。コード５４５は、マルチスレッドアプリケーションのソースコード、マルチスレッドアプリケーションのソースコードの中間表現（「ＩＲ」）、マルチスレッドアプリケーションの実行ファイルなどとすることができる。いくつかの実施形態において、量子ビルダコンポーネント５０５は、マルチスレッドアプリケーションコード５４５内に同期コードを挿入して、コンパイラによって生成される制御フローグラフ（「ＣＦＧ」）において操作を追跡することによって、コンパイラを使用して量子を構築することができる。挿入されたコードは、量子サイズを追跡し、量子サイズに到達したとき、ＤＭＰコンポーネント５１０によって提供される１つまたは複数の関数を呼び出して、アプリケーション内のスレッドの前進を制御する。ＤＭＰコンポーネント５１０は、ランタイムシステムを提供することができ、および／またはＤＭＰ関数５１５〜５４０のうちの１つまたは複数をコード５４５に挿入することができる。いくつかの実施形態において、決定論的プロセッシングシステム５００は、トランザクショナルメモリシステムと共に動作し、および／または共有テーブルを実装する。]
[0086] 示された実施形態において、ＤＭＰライブラリは、ＤＭＰ開始関数（「ＤＭＰ＿Ｆｕｎｃｔｉｏｎ＿Ｓｔａｒｔ（）関数５１５」）、ＤＭＰ初期化関数（「ＤＭＰ＿Ｉｎｉｔ（）関数５２０」）、ＤＭＰ格納関数（「ＤＭＰ＿Ｓｔｏｒｅ（）関数５２５」）、ＤＭＰロード関数（「ＤＭＰ＿Ｌｏａｄ（）関数５３０」）、ＤＭＰコミット関数（「ＤＭＰ＿Ｃｏｍｍｉｔ（）関数５３５」）、およびＤＭＰ終了関数（「ＤＭＰ＿Ｆｕｎｃｔｉｏｎ＿Ｅｎｄ（）関数５４０」）を含む。ＤＭＰ開始関数５１５および終了関数５４０は、アプリケーション関数が開始し、終了するときを画定するために使用され得る。ＤＭＰロード関数５３０は、ロード操作が実行される、または実行された決定論的マルチプロセッシングシステム５００に運ぶために使用され得る。同様に、ＤＭＰ格納関数５２５は、格納操作が実行される、または実行された決定論的マルチプロセッシングシステム５００に運ぶために使用され得る。ＤＭＰ格納関数５２５およびロード関数５３０は、メモリ操作の順序を制御し、それによってこうした操作の決定論的実行を実施するために使用される。ＤＭＰ初期化関数５２０およびＤＭＰコミット関数５３５は、メモリ操作の順序を制御する、またはトランザクションを開始し、または終了するために使用されるコードのブロックを画定するために使用され得る。ＤＭＰコンポーネント５１０によって提供される関数は様々な方法で変更され得ることを、当業者であれば理解されたい。例えば、いくつかの関数がマージまたは分割されてもよく、いくつかの関数が省略されてもよく、いくつかの関数が追加されてもよい。]
[0087] いくつかの実施形態において、量子ビルダコンポーネント５０５は、以下の表２に列挙されるＤＭＰコンポーネント５１０の関数５１５〜５４０を挿入する。]
[0088] ]
[0089] いくつかの実施形態において、量子ビルダコンポーネント５０５は、増補されたコードの中間表現を作成し、これは、例えば、制御フローグラフ（「ＣＦＧ」）として表され得る。図１１は、表２に従って増補されるマルチスレッドアプリケーションコード５４５の関数の制御フローグラフの一例を示す。いくつかの実施形態において、マルチスレッドアプリケーションコード５４５が増補された後、コンパイラは、例えばＤＭＰ関数５１５〜５４０への呼び出しをインライン化することによって、増補されたコードを再度最適化する。コンパイラは本明細書では具体的に記載されない増補されたコードへの他の最適化を実行することができることを、当業者であれば理解されたい。] 図１１
[0090] いくつかの実施形態において、マルチスレッドアプリケーションコード５４５は、ＳＴＭ、ＨＴＭ、またはＨＳ−ＴＭなど、トランザクショナルメモリシステムを使用して、スレッドによる共有リソースへのアクセスを制御する。こうした実施形態において、決定論的マルチプロセッシングシステム５００は、トランザクションがマルチスレッドアプリケーションのスレッドによってコミットされる順序を制御するために使用され得る。例えば、量子ビルダ５０５は、ＤＭＰ初期化関数５２０およびＤＭＰコミット関数５３５への呼び出しを挿入することによってトランザクションにおける各量子を包むことができる。別の例として、マルチスレッドアプリケーションコード５４５が１つまたは複数のアプリケーションレベルトランザクショナルメモリブロックを含むとき、量子ビルダコンポーネント５０５は、ソフトウェア開発者によって宣言される各アトミックブロックの前にＤＭＰ初期化関数５２０への呼び出しを挿入することによって、また命令をコミットするためのＴＭシステムへの任意の呼び出しの前にＤＭＰコミット関数５３５への呼び出しを挿入することによって、マルチスレッドアプリケーションコード５４５を増補することができる。さらに別の例として、決定論的マルチプロセッシングシステム５００は、ＴＭインターフェイスの関数への呼び出しをＤＭＰコンポーネント５１０の１つまたは複数の関数５１５〜５４０への呼び出しで包むことによって、ＴＭシステムによって提供されるインターフェイスを増補することができる。その結果、決定論的マルチプロセッシングシステム５００がＴＭシステムと共に動作するとき、トランザクションは、決定論的に開始され、および／またはコミットされ得る。トランザクショナルメモリシステムがＨＴＭシステムであるとき、ＨＴＭがこうした追跡を実行する限り、ＤＭＰロード関数５３０およびＤＭＰ格納関数５２５が含まれる必要はないことに留意されたい。]
[0091] いくつかの実施形態において、マルチスレッドアプリケーションコード５４５は、実行可能な増補されたアプリケーション５５０にコンパイルされる。一方、他の実施形態では、増補されたアプリケーション５５０は、マシンに依存しない中間言語コードであり、これは、実行時に実行可能命令に変換される。増補後、増補されたアプリケーション５５０は、マルチプロセッシングシステム上で決定論的に実行され得る。すなわち、増補されたアプリケーション５５０に同じ入力が与えられると、マルチプロセッシングシステムは、スレッド量子を決定論的にインターリーブし、それによって、増補されたアプリケーション５５０が実行されるたびに同じ入力を生成する。図５に示されるコンポーネントは様々な方法で変更され得ることを、当業者であれば理解されたい。例えば、コンパイラなど、いくつかのコンポーネントがマージまたは分割されてもよく、いくつかのコンポーネントが省略されてもよく、いくつかのコンポーネントが追加されてもよい。] 図５
[0092] いくつかの実施形態において、ＤＭＰコンポーネント５１０によって提供される関数５１５〜５４０は、マルチスレッドアプリケーションのスレッド間に決定論的にトークンを渡し、または進め、それによって各スレッドの前進を決定論的に制御する責任を負う。いくつかの実施形態において、これは、スレッドデータ構造６００を使用することによって達成される。図６は、１つまたは複数の実施形態において、マルチプロセッサコードを決定論的にするためにファシリティによって使用されるスレッドデータ構造６００を示す高レベルブロック図である。いくつかの実施形態において、スレッドデータ構造６００は、スレッドコンテナ６０５を含む。スレッドコンテナは、実行中にマルチスレッドアプリケーションによって作成されるスレッドごとにスレッドＩＤを格納する。スレッドコンテナ６０５は、配列、リンクリスト、キュー、またはスレッドＩＤの他のデータ構造として実装され得る。] 図６
[0093] いくつかの実施形態において、スレッドデータ構造６００は、実行中にマルチスレッドアプリケーションのスレッドによるトランザクションまたは制御された操作の実行の順序を制御するために使用されるトークン６１０を含む。例えば、いくつかの実施形態において、制御された操作を実行する、またはトランザクションをコミットする前に、スレッドは、そのスレッドＩＤがトークン６１０の現在の値に一致するかどうかを決定する。トークン６１０の現在の値がスレッドＩＤに一致するとき、対応するスレッドは、制御された操作を実行する、またはトランザクションをコミットしようと試行することができる。そうでない場合、対応するスレッドは、トークン６１０の現在の値がそのスレッドＩＤに一致するまで待つ。]
[0094] いくつかの実施形態において、スレッドが作成される順序は、スレッドが決定論的に実行される順序に対応する。例えば、各スレッドが作成されるとき、スレッドの対応するスレッドＩＤは、スレッドコンテナ６０５に順次格納され得る。トランザクションまたは制御された操作が実行されるとき、実行中のスレッドが、例えばＤＭＰ＿Ｃｏｍｍｉｔ（）５３５などいくつかのＤＭＰ関数を呼び出し、こうした関数は、（第１のスレッドＩＤで開始して）スレッドＩＤが格納されたシーケンスに基づいてスレッドコンテナ６０５に格納されたスレッドＩＤを順次ループすることによって、トークン６１０の値を進めるように動作する。スレッドが終了すると、スレッドの対応するＩＤはスレッドコンテナ６０５から削除されることに留意されたい。]
[0095] いくつかの実施形態において、スレッドデータ構造は、コミットブロックサイズ６１５を格納する。コミットブロックサイズ６１５は、トークンが進められる前に、スレッドＩＤがトークン６１０の現在の値に一致するスレッドによって実行され得る予め定められた数のトランザクションまたは制御された操作を表す。コミットブロックサイズ６１５は、１つのトランザクションまたは制御された操作からＮ個のトランザクションまたは制御された操作まで及び得る。少なくとも１つの実施形態において、コミットブロックサイズ６１５は、１，０００に等しい。いくつかの実施形態において、コミットブロックサイズ６１５は、構成可能である。例えば、コミットブロックサイズ６１５は、マルチスレッドアプリケーションの様々なスレッドインターリービングをプログラム的に操作し、テストするように、ソフトウェア開発者によって構成され得る。別の例として、コミットブロックサイズ６１５は、マルチスレッドアプリケーションによって作成され得る最大数のスレッド、および／またはマルチスレッドアプリケーションが実行するマルチプロセッシングシステムのプロセッサまたはコアの数に基づいて、自動的に構成され得る。]
[0096] スレッドによって実行される制御された操作の数をカウントするために様々な技術が使用され得ることを、当業者であれば理解されたい。いくつかの実施形態において、スレッドデータ構造６００は、スレッドコミットブロック６２０を含む。スレッドコミットブロック６２０は、スレッドＩＤが現在のトークンＩＤ６１０に一致するスレッドによって実行された制御された操作の数を表し得る。スレッドが制御された操作を実行するたびに、スレッドコミットブロック６２０の値は、増分され、コミットブロックサイズ６１５と比較される。スレッドコミットブロック６２０の値がコミットブロックサイズ６１５に等しい場合、トークン６０５は、次のスレッドＩＤに進められ、スレッドコミットブロック６２０の値は、ゼロにリセットされる。代替例として、スレッドコミットブロック６２０は、スレッドがその対応するトランザクションをコミットしようと試行する前に残っているブロックの数を表し得る。こうした実施形態において、スレッドコミットブロック６２０は、スレッドコンテナ６０５に格納されたスレッドＩＤを有するスレッドごとに残りのブロックの数を含み得る。次いで、スレッドは、ブロックを実行するたびに、その対応するスレッドコミットブロックを減分し、残りのブロックの数がゼロに等しいとき、そのトランザクションをコミットしようと試みる。]
[0097] いくつかの実施形態において、スレッドデータ構造は、使用中スレッドブロック６２５を含み、これは、マルチスレッドアプリケーションで実行中のスレッドの数を表す。いくつかの実施形態において、使用中スレッドブロック６２５は、スレッドが作成されるたびに増分される。同様に、使用中スレッドブロック６２５は、スレッドが終了するたびに減分される。一方、他の実施形態では、使用中スレッドブロック６２５は、スレッドコンテナ６０５のサイズに基づいて決定される。図６に示されるスレッドデータ構造６００は様々な方法で変更され得ることを、当業者であれば理解されたい。例えば、いくつかの部分がマージまたは分割されてもよく、いくつかの部分が省略されてもよく、いくつかの部分が追加されてもよい。] 図６
[0098] 図７は、１つまたは複数の実施形態における、スレッドを作成し、決定論的に実行する一例を示す高レベル図である。説明を容易にするために、ある期間にわたるスレッドデータ構造６００の一部分の内容が示される。トークン値６１０によって示されるように、スレッドが作成される順序は、スレッドが決定論的に実行される順序に対応する。] 図７
[0099] 示された例において、最初に作成されたスレッド（「スレッド１」）は、マルチスレッドアプリケーションのメインのアプリケーションスレッドを表す。説明を容易にするために、各スレッドのスレッドＩＤは、スレッドが作成された順序に等しい。すなわち、最初に作成されたスレッドのスレッドＩＤは１、２番目に作成されたスレッドのスレッドＩＤは２、３番目に作成されたスレッドのスレッドＩＤは３、などとなる。時刻Ｔ０とＴ１との間で、スレッド１が実行し、スレッド２が作成される。示された例において、スレッドの実行は、指定された数の制御された操作（例えば、コミットブロックサイズ６１５によって指定された量子）によって表される。したがって、図７に示される時間の増分は、必ずしも等しくない。各スレッドによって実行された未制御の操作の数は、異なっていてもよく、またその各実行期間中にスレッドごとに異なっていてもよいことにも留意されたい。] 図７
[0100] 図７に戻って、スレッド１がその量子の実行を終了する前のある時点でスレッド２が作成されたため、時刻Ｔ０とＴ１との間の使用中スレッド６２５の数は２である。その結果、スレッド１が終了すると、トークン６１０は、スレッドコンテナ６０５に格納された次のスレッドＩＤに進められた（すなわち、スレッド２）。] 図７
[0101] 時刻Ｔ１とＴ２との間で、スレッド２が実行し、次いでトークン６１０がスレッド１に戻される。時刻Ｔ２とＴ３との間で、スレッド１が実行し、次いでトークン６１０がスレッド２に進められる。時刻Ｔ３とＴ４との間で、スレッド２が実行し、次いでトークン６１０がスレッド１に戻される。]
[0102] 時刻Ｔ４とＴ５との間で、スレッド１が実行し、スレッド２が作成される。時刻Ｔ４とＴ５との間でスレッド３が作成されるが、スレッド２は、時刻Ｔ５とＴ６との間で実行する。これは、スレッドが作成された順序が、スレッドが実行される順序に対応するからである。その結果、時刻Ｔ５とＴ６との間でスレッド２が実行し、次いで、トークン６１０がスレッド３に進められる。次いで時刻Ｔ６とＴ７との間でスレッド３が実行し、次いでトークン６１０がスレッド１に戻される。]
[0103] 図８は、１つまたは複数の実施形態における、マルチプロセッサコードを決定論的にするためにトランザクショナルメモリシステムを使用する一例を示す高レベルブロック図である。説明を容易にするために、ある期間にわたるスレッドデータ構造６００の一部分の内容が示される。また、説明を容易にするために、スレッドＩＤがスレッド１、スレッド２、スレッド３などのようにスレッドコンテナ６０５に配列されると仮定する。ある期間にわたってトークン値６１０によって示されるように、スレッドがトランザクションをコミットする順序は、決定論的である。説明を容易にするために、トークン６１０の最初の値は、スレッド１のスレッドＩＤに対応する。示された例において、各スレッドによって実行されるトランザクションは、サイズが決定論的である。すなわち、各スレッドは、特定の数のブロックを実行する。説明を容易にするために、コミットブロックサイズ６１５は２である。] 図８
[0104] 示されるように、時刻Ｔ０において、スレッド１〜３がトランザクションを開始する。スレッドがその対応するトランザクションを終了した後、スレッドは、そのトランザクションを決定論的にコミットしようと試行する。いくつかの実施形態において、各スレッドは、そのトランザクションが、スレッドにそのトランザクションをコミットさせないようにする競合をもたらしたかどうかを決定する。一方、他の実施形態では、この決定は、そのスレッドＩＤがトークン６１０の現在の値に一致するとき、スレッドによって行われる。例えば、これは、ＳＴＭＶａｌｉｄＴｒａｎｓａｃｔｉｏｎ（）を呼び出すことによって達成され得る。]
[0105] 時刻Ｔ１で、トークン６１０の現在の値は、スレッド１のＩＤに一致する。したがって、示された例では、スレッド１は、そのトランザクションが、それにトランザクションをコミットさせないようにする競合をもたらしたかどうかを決定する。指定された決定論的順序に従ってトランザクションがコミットされるため、ファシリティは、書き込み後書き込み、読み取り後書き込みの競合の結果、トランザクションの中止を回避するために残っているメモリを使用することができる。すなわち、トランザクションがコミットされる前にトランザクション内の操作がバッファに入れられるため、ファシリティは、両方のトランザクションを中止するのではなく、書き込み後書き込みまたは読み取り後書き込み操作が実際に競合するかどうかを決定することができる。示された例では、スレッド１およびスレッド２は、同じ共有メモリロケーション（すなわち、アドレスＡ）にアクセスしており、これは従来のトランザクショナルメモリシステムにおける読み込み後書き込みをもたらすことになるが、スレッド１のトランザクションは有効である。これは、スレッド１がアドレスＡに値を格納し、トークン６１０がそのスレッドＩＤに一致するからである。すなわち、（スレッド１によって実行される）Ａの格納は、（スレッド２によって実行される）Ａのロードによって影響されない。その結果、スレッド１は、そのトランザクションをコミットし（例えば、ＳＴＭＣｏｍｍｉｔＴｒａｎｓａｃｔｉｏｎ（）を呼び出すことによって）、次いでトークン６１０は、次のスレッドＩＤに進められる。しかし、トークン６１０は、スレッド２のスレッドＩＤに一致した場合、スレッド１は、そのトランザクションを中止することになる。これは、スレッド１がＡを格納した後、スレッド２がＡをロードしたかもしれないからである。トークン６１０がスレッド２のＩＤに一致すると仮定すると、スレッド１およびスレッド２は、そのトランザクションを中止することになる。この場合、スレッド２は、スレッド１の中止されたトランザクションを再開する前に、中止されたトランザクションを開始し、コミットすることになる。]
[0106] 示されるように、時刻Ｔ１で、スレッド１は、そのトランザクションをコミットし、次いでトークン６１０は、スレッド２に進められる。しかし、スレッド２は、そのトランザクションをコミットすることができない。というのは、スレッド２は、同じトランザクション中にスレッド１によって格納された値をロードしたからである。すなわち、スレッド２は、スレッド１がＡを格納する前に、Ａをロードしたかもしれない。その結果、スレッド２は、そのトランザクションを中止し、再開しなければならない。示された例において、中止されたスレッド以降のスレッドＩＤを有するすべてのスレッドが中止される。一方、他の実施形態では、並行のトランザクションが同じ共有リソースにアクセスした以降のＩＤを有するスレッドのみが中止され、再開される。したがって、示された例では、スレッド３のトランザクションは、中止され、再開される。しかし、他の実施形態において、スレッド３のトランザクションは、中止されない。というのは、そのトランザクションは、並行のトランザクション中にスレッド２またはスレッド１によってアクセスされた共有リソースにアクセスしなかったからである。代わりに、スレッド３は、単にトークン６１０がそのスレッドＩＤに一致するのを待つことになる。スレッドＩＤがトークンに一致するスレッドが、その対応するトランザクションを正常にコミットするまで、トークン６１０は進められないことに留意されたい。]
[0107] 示されるように、時刻Ｔ３で、スレッド２〜３は、その中止されたトランザクションを再開する。時刻Ｔ４で、トークン６１０の現在の値は、スレッド２のＩＤに一致するため、スレッド２は、その再開されたトランザクションが、それにトランザクションをコミットさせない競合をもたらしたかどうかを決定する。示された例において、スレッド２および３の再開されたトランザクションは、任意の共有メモリロケーションにアクセスしない。その結果、時刻Ｔ４で、スレッド２は、そのトランザクションを正常にコミットし、次いでトークン６１０は、スレッド３に進められる。時刻Ｔ５で、スレッド３は、そのトランザクションを正常にコミットし、次いでトークン６１０は、スレッド１に戻される。]
[0108] 次に、時刻Ｔ６で、スレッド１〜３は、トランザクションを開始し、プロセスは上述したように続行する。時刻Ｔ６で、スレッド１および３の並行のトランザクションによって、スレッド３がそのトランザクションを中止し、再開することに留意されたい。しかし、スレッド１および２は、決定論的にコミットし、トークン６１０は、上述したように、スレッド３に進められる。]
[0109] いくつかの実施形態において、コミットされない（「推測的な」）データはスレッド間に転送され、それによって中止されたトランザクションの数を低減し、マルチスレッドアプリケーション内のさらなる並行性を回復する。例えば、図２１は、１つまたは複数の実施形態における、トランザクショナルメモリ（ＴＭ）フォワーディングの一例を示す高レベル図である。説明を容易にするために、ある期間にわたるスレッドデータ構造６００の一部分の内容が示される。また、説明を容易にするために、スレッドＩＤがスレッド１、スレッド２、スレッド３などのようにスレッドコンテナ６０５に配列されると仮定する。ある期間にわたってトークン値６１０によって示されるように、スレッドがトランザクションをコミットする順序は、決定論的である。説明を容易にするために、トークン６１０の最初の値は、スレッド１のスレッドＩＤに対応する。] 図２１
[0110] ＴＭフォワーディングが有効にされ、スレッド（「アップデータ」スレッドと呼ばれる）が、別のスレッドに対して共有またはプライベートと見なされるメモリロケーションに書き込むためのメモリロケーションを発行すると、アップデータスレッドは、メモリロケーションに格納されたデータが更新されたことを示すメッセージをブロードキャストする。ブロードキャストに応答して、データの古くなったコピーを含む各スレッドは、そのキャッシュから古くなったデータを削除する。いくつかの実施形態において、別のスレッド（「呼び出し側」スレッドと呼ばれる）が共有メモリロケーションを読み取るためのメモリ操作を順次発行した場合、データの更新されたコピーは、アップデータスレッドが決定論的順序で呼び出し側スレッドに先行することを条件に、トランザクションの中止の代わりに、呼び出し側スレッドに転送される。例えば、示された実施形態において、時刻Ｔ０で、スレッド１〜３は、トランザクションを開始する。スレッド１は、メモリロケーションＡに書き込むためのメモリ操作を発行し、メモリロケーションＡに格納されたデータが更新されたことを示すメッセージをブロードキャストする。説明を容易にするために、スレッド２は、メモリロケーションＡに格納されたデータを以前キャッシュに入れたと仮定する。スレッド２がスレッド１からブロードキャストを受信すると、スレッド２は、そのキャッシュからデータの古くなったコピーを削除する。スレッド２は、メモリロケーションＡを読み取るためのメモリ操作を順次発行する。データはもはやキャッシュに入れられていないため、スレッド２は、メモリロケーションＡが更新されたかどうかを決定し、そうである場合、決定論的順序でそれに先行するスレッドによってそれが更新されたかどうかを決定する。この例で、決定論的順序でスレッド１がスレッド２に先行するため、スレッド１によってメモリロケーションＡに格納されるべきデータの更新されたコピーは、スレッド２に転送される。スレッド２に転送されたデータは、推測的である。というのは、スレッド１は、データがスレッド２によって受信されたときにそのトランザクションをコミットしていないからである。いくつかの実施形態において、推測的なデータが、最終的に中止されるコミットされていないトランザクションから転送される場合、推測的なデータを消費したすべてのスレッドも中止される。すなわち、スレッド１がそのトランザクションを中止する場合、スレッド２もそのトランザクションを中止する。というのは、それがスレッド１から推測的なデータを消費したからである。]
[0111] スレッド１〜３が対応するトランザクションを終了した後、各スレッドは、そのトランザクションをコミットしようと試行する。時刻Ｔ１で、トークン６１０の現在の値は、スレッド１のＩＤに一致し、スレッド１にそのトランザクションをコミットさせない競合は存在しない。したがって、スレッド１は、時刻Ｔ１でそのトランザクションをコミットし、次いでトークン６１０は、決定論的順序で次のスレッドＩＤに進められる（すなわちスレッド２）。時刻Ｔ２で、トークン６１０の現在の値は、スレッド２のＩＤに一致し、スレッド２にそのトランザクションをコミットさせない競合は存在しない。すなわち、スレッド１が、推測的データが以前スレッド２に転送されたトランザクションを正常にコミットしたため、スレッド２にそのトランザクションをコミットさせないための競合は存在しない。したがって、時刻Ｔ２で、スレッド２は、そのトランザクションをコミットし、トークン６１０は、決定論的順序で次のスレッドＩＤに進められる（すなわちスレッド３）。時刻Ｔ３で、トークン６１０の現在の値は、スレッド３のＩＤに一致し、スレッド３にそのトランザクションをコミットさせない競合は存在しない。その結果、スレッド３は、時刻Ｔ３でそのトランザクションをコミットし、トークン６１０は、決定論的順序で次のスレッドＩＤに進められる（すなわちスレッド１）。次に、時刻Ｔ４で、スレッド１〜３は、トランザクションを開始し、プロセスは上述したように続行する。]
[0112] 図２２は、１つまたは複数の実施形態における、ファシリティによって実行されるトランザクショナルメモリフォワーディングプロセス２２００を示すフロー図である。トランザクショナルメモリシステムは、ハードウェアトランザクショナルメモリ（ＨＴＭ）システム、ソフトウェアトランザクショナルメモリ（ＳＴＭ）システム、またはハイブリッドハードウェア−ソフトウェアトランザクショナルメモリシステム（ＨＳ−ＴＭ）とすることができることに留意されたい。ステップ２２０５〜２２６０で、ファシリティは、呼び出し側スレッドのトランザクション内の各操作をループする。ステップ２２０５で、ファシリティは、操作を選択する。ステップ２２１０で、選択された操作が格納操作である場合、ファシリティはステップ２２１５に進み、そうでない場合、ファシリティはステップ２２２５に進む。] 図２２
[0113] ステップ２２１５で、ファシリティは、格納操作を反映するために、呼び出し側スレッドのキャッシュを更新する。ステップ２２２０で、ファシリティは、格納操作によって指定されたメモリロケーションに格納されたデータが更新されたことを示すブロードキャストメッセージを送信し、次いでステップ２２６０に進む。ステップ２２６０で、トランザクション内の追加の操作が残っている場合、ファシリティはステップ２２０５に進み、そうでない場合、プロセス２２００は戻る。いくつかの実施形態において、こうしたブロードキャストされたメッセージが受信されると、ファシリティは、現在のトランザクション中にスレッドが更新されたメモリロケーションにアクセスしたかどうかをスレッドごとに決定する。現在のトランザクション中にスレッドがメモリロケーションにアクセスしていない場合、メッセージは、そのスレッドについて無視される。そうではなく、現在のトランザクション中にスレッドがメモリロケーションにアクセスした場合、ファシリティは、スレッドが決定論的順序でアップデータスレッドに先行するかどうかを決定する。スレッドが決定論的順序でアップデータスレッドに先行する場合、メッセージは、スレッドについて無視される。そうではなく、スレッドが決定論的順序でアップデータスレッドに先行しない場合、ファシリティは、そのスレッドによって実行されたトランザクションを中止する。]
[0114] ステップ２２２５で、操作がロード操作である場合、ファシリティはステップ２３３０に進み、そうでない場合、ファシリティはステップ２２６０に進む。ステップ２２３０で、ロード操作によって指定されたメモリロケーションが呼び出し側スレッドによってキャッシュに入れられる場合、ファシリティはステップ２２３５に進み、そうでない場合、ファシリティはステップ２２４０に進む。ステップ２２３５で、ファシリティは、呼び出し側スレッドのキャッシュからデータをロードし、次いでステップ２２６０に進む。ステップ２２４０で、別のスレッド（「アップデータスレッド」と呼ばれる）によるトランザクション中にメモリロケーションが更新された場合、ファシリティはステップ２２４５に進み、そうでない場合、ファシリティはステップ２２５５に進む。]
[0115] ステップ２２４５で、アップデータスレッドが決定論的順序で呼び出し側スレッドに先行する場合、ファシリティはステップ２２５０に進み、そうでない場合、ファシリティはステップ２２５５に進む。ステップ２２５０で、ファシリティは、ロード操作によって指定されたメモリロケーションに格納されたデータを、アップデータスレッドのキャッシュから呼び出し側スレッドに転送し、次いで、ファシリティはステップ２２６０に進む。ステップ２２５５で、ファシリティは、メモリからロード操作によって指定されたメモリロケーションに格納されたデータをロードし、次いでステップ２２６０に進む。ステップ２２６０で、トランザクション内の追加の操作が残っている場合、ファシリティはステップ２２０５に進み、そうでない場合、プロセス２２００は戻る。]
[0116] 図９は、１つまたは複数の実施形態において、マルチスレッドアプリケーションコードを増補するためにファシリティによって実行されるプロセス９００を示すフロー図である。ステップ９０５〜９４０で、ファシリティは、マルチスレッドアプリケーションコード５４５の各関数をループする。ステップ９０５で、ファシリティは、関数を選択し、次いでステップ９１０に進む。ステップ９１０で、ファシリティは、ＤＭＰ＿Ｆｕｎｃｔｉｏｎ＿Ｓｔａｒｔ（）関数５１５など、決定論的マルチプロセッシング起動関数を挿入し、次いでステップ９１５に進む。ステップ９１５で、ファシリティは、ＤＭＰ＿Ｉｎｉｔ（）関数５２０など、決定論的マルチプロセッシング初期化関数を挿入し、次いでステップ９２０に進む。ステップ９２０〜９３０で、ファシリティは、選択されたアプリケーションの各ブロックをループする。ステップ９２０で、ファシリティは、ブロックを選択し、次いでステップ９２５に進む。ステップ９２５で、ファシリティは、構文解析ブロック関数１０００を呼び出し、次いでステップ９３０に進む。ステップ９３０で、追加のブロックが残っている場合、ファシリティはステップ９２０に進み、そうでない場合、ファシリティはステップ９３５に進む。ステップ９３５で、ファシリティは、ＤＭＰ＿Ｆｕｎｃｔｉｏｎ＿Ｅｎｄ（）５４０など、決定論的プロセッシング終了関数を挿入し、次いでステップ９４０に進む。ステップ９４０で、追加の関数が残っている場合、ファシリティはステップ９０５に進み、そうでない場合、これらのステップは終了する。] 図９
[0117] 図１０は、１つまたは複数の実施形態における、ブロックを構文解析するためにファシリティによって実行されるプロセス１０００を示すフロー図である。ステップ１００５で、ブロックがロードブロックであることをファシリティが決定した場合、ファシリティはステップ１０１０に進み、そうでない場合、ファシリティはステップ１０１５に進む。ステップ１０１０で、ファシリティは、ロードブロックの前にＤＭＰ＿Ｌｏａｄ（）関数５３０への呼び出しを挿入し、次いでファシリティは戻る。ステップ１０１５で、ブロックが格納ブロックであることをファシリティが決定した場合、ファシリティはステップ１０２０に進み、そうでない場合、ファシリティはステップ１０２５に進む。ステップ１０２０で、ファシリティは、格納ブロックの前にＤＭＰ＿Ｓｔｏｒｅ（）関数５２５への呼び出しを挿入し、次いでファシリティは戻る。ステップ１０２５で、ブロックがジャンプブロックであることをファシリティが決定した場合、ファシリティはステップ１０３０に進み、そうでない場合、ファシリティはステップ１０３５に進む。ステップ１０３０で、ファシリティは、ジャンプの前にＤＭＰ＿Ｃｏｍｍｉｔ（）関数５３５への呼び出しを挿入し、ジャンプ先ポイントでＤＭＰ＿Ｉｎｉｔ（）関数５２０への呼び出しを挿入し、次いでファシリティは戻る。ステップ１０３５で、ブロックが関数呼び出しであることをファシリティが決定した場合、ファシリティはステップ１０４０に進み、そうでない場合、ファシリティはステップ１０４５に進む。ステップ１０４０で、ファシリティは、呼び出し前にＤＭＰ＿Ｃｏｍｍｉｔ（）関数５３５への呼び出しを挿入し、呼び出し後ＤＭＰ＿Ｉｎｉｔ（）５２０への呼び出しを挿入し、次いでファシリティは戻る。ステップ１０４５で、ブロックがＩ／Ｏ呼び出しであることをファシリティが決定した場合、ファシリティは、上述したようにステップ１０４０に進み、そうでない場合、ファシリティはステップ１０５０に進む。ステップ１０５０で、ブロックが戻りブロックであることをファシリティが決定した場合、ファシリティはステップ１０５５に進み、そうでない場合、ファシリティは戻る。ステップ１０５５で、ファシリティは、戻りブロック前にＤＭＰ＿Ｃｏｍｍｉｔ（）５３５への呼び出しを挿入し、次いでファシリティは戻る。] 図１０
[0118] 図１１は、１つまたは複数の実施形態における、マルチスレッドアプリケーションの増補された関数の制御フローグラフ１１００の一例である。「制御フローグラフ」という用語は、その実行中にアプリケーションによってトラバースされ得るすべてのパスの表現を指す。グラフ１１００における各ノード１１０５〜１１３０は、基本ブロック、すなわち、任意のジャンプまたはジャンプターゲットのない直線のコードを表す。ジャンプターゲットは、ブロックを開始し、ジャンプは、ブロックを終了させる。例えば、ＤＭＰ＿Ｉｎｉｔ（）関数５２０を表すブロック１１１０は、ジャンプターゲットである。ブロック１１０５は、入口ブロックを表し、そこを通ってすべての制御がフローグラフに入る。ブロック１１３０は、出口ブロックを表し、そこを通ってすべての制御フローが出る。有向辺、例えば、ブロック１１１５と１１２５との間の辺、１１２０と１１２５との間の辺、およびブロック１１１０とブロック１１１５、１１２０、および１１２５との間の辺は、制御フローにおいてジャンプを表すために使用される。] 図１１
[0119] 図１２は、１つまたは複数の実施形態における、決定論的マルチプロセッシング（「ＤＭＰ」）初期化関数１２００を示すフロー図である。例えば、ＤＭＰ初期化関数１２００は、ファシリティがトランザクショナルメモリシステムと共に動作するとき、実行され得る。ＤＭＰ初期化関数は、スレッドがトランザクションの処置を開始または続行できるように、スレッドが初期化された状態であるかどうかを決定するために実行され得る。スレッドが初期化されない（すなわち、スレッドのｉｎｉｔＳｉｔｅ変数の値がゼロに等しい）場合、その実行は、トークンの値がスレッドＩＤに一致するまで一時停止される。スレッドが初期化された場合、スレッドは実行を続ける。] 図１２
[0120] ステップ１２０５で、ファシリティは、スレッド開始変数（「ｉｎｉｔＳｉｔｅ」）の値がゼロに等しいことを決定した場合、ファシリティはステップ１２１０に進み、そうでない場合、ファシリティは戻る。スレッドの初期化変数は、例えば、スレッドが正常にトランザクションをコミットした後、ゼロに割り当てることができる。ステップ１２１０で、トークンの現在の値がスレッドＩＤに一致することをファシリティが決定した場合、ファシリティはステップ１２１５に進み、そうでない場合、ファシリティは折り返してステップ１２１０に戻る。すなわち、ファシリティは、スレッドＩＤがトークンの値に一致するまで、ステップ１２１０におけるスレッド実行を一時停止する。ステップ１２１５で、ファシリティは、ｉｎｉｔＳｉｔｅ変数を、スレッドがトランザクションを開始するメモリアドレスに割り当て、次いでファシリティは戻る。次いでｉｎｉｔＳｉｔｅ変数は、トランザクションをコミットできない場合、明示的なジャンプアドレスとして使用され得る。]
[0121] 図１３は、１つまたは複数の実施形態における、決定論的マルチプロセッシング（「ＤＭＰ」）コミット関数１３００を示すフロー図である。例えば、ＤＭＰコミット関数１３００は、ファシリティがトランザクショナルメモリシステムと共に動作するとき、実行され得る。ステップ１３０５で、ファシリティは、コミットブロック変数の値を減分し、次いでステップ１３１０に進む。コミットブロック変数は、スレッドによって実行された操作の数をカウントするために使用される。ステップ１３１０で、コミットブロック変数の値がゼロであることをファシリティが決定した場合、ファシリティはステップ１３１５に進み、そうでない場合、ファシリティは戻る。ステップ１３１５で、ファシリティが間に競合があったことを決定した（例えば、トランザクション中に別のスレッドによって書き込まれたロケーションからスレッドが読み取ったため）場合、ファシリティはステップ１３２０に進み、そうでない場合、ファシリティはステップ１３２５に進む。ステップ１３２０で、ファシリティはトランザクションを中止する。ステップ１３２５で、ファシリティは、トランザクションをコミットし、次いでステップ１３３０に進む。ステップ１３３０で、ファシリティは、スレッドのｉｎｔｉＳｉｔｅ変数の値をゼロに割り当て、次いでステップ１３３５に進む。ステップ１３３５で、ファシリティは、コミットブロック変数の値をコミットブロックサイズに割り当てることによって、スレッドのコミットブロック変数の値をリセットし、次いで、ステップ１３４０に進む。ステップ１３４０で、ファシリティは、トークンの値を次のスレッドＩＤの値に割り当てることによって、トークンを進め、次いでファシリティは戻る。] 図１３
[0122] このように、マルチスレッドアプリケーションの決定論的マルチプロセッシングのためのファシリティについて説明した。ファシリティについて、特定の実施形態を参照して説明してきたが、ファシリティは、記載した実施形態に限定されず、添付の特許請求の範囲の意図および範囲内の修正および変更で実施することができることを理解されたい。したがって、明細書および図面は、制限的意味ではなく、例示的意味でみなされるものとする。]

权利要求:

請求項1
マルチスレッドアプリケーションのクリティカルパス（critical path）において前記マルチスレッドアプリケーションのスレッドのインターリービング(interleaving)を制御するためのマルチプロセッシングシステムであって、複数のスレッドを指定するマルチスレッドアプリケーションコードと、前記マルチスレッドアプリケーションコードを、それぞれ予め定められた数の操作(operations)から成る２つ以上の量子(quanta)に分割(divide)するための量子ビルダコンポーネント(quantum builder component)と、同期コード(synchronization code)が前記マルチスレッドアプリケーションのスレッドに前記２つ以上の量子を実行させる決定論的順序(deterministic order)を指定(specify)するための決定論的(deterministic)実行コンポーネント(execution component)と、スレッド実行を監視(monitor)し、その予め定められた数の操作を実行する前に、前記同期コードを呼び出すかどうかを決定するための適応(adaptive)量子ビルダコンポーネントと、スレッドの実行を監視し、前記同期コードが前記適応量子ビルダコンポーネントによって呼び出されない場合、スレッドがその予め定められた数の操作(operations)を実行することに応答して前記同期コードを呼び出す(invoke)ための量子完了(completion)コンポーネントとを含み、前記マルチスレッドアプリケーションコードの複数の実行パスについて特定の入力が指定されたとき、各実行パス(execution pass)が前記特定の入力について同じ出力を生成(produces)するマルチプロセッシングシステム。
請求項2
前記適応量子ビルダコンポーネントが、アプリケーションレベルの同期プリミティブ(primitive)への変更について、スレッドの実行を監視する請求項１に記載のマルチプロセッシングシステム。
請求項3
アプリケーションレベル同期プリミティブへの前記変更がロック(lock)の解除(release)である請求項２に記載のマルチプロセッシングシステム。
請求項4
前記ロックが解除されると、前記適応量子ビルダコンポーネントが前記量子境界(boundary)を終了(ends)させる請求項２に記載のマルチプロセッシングシステム。
請求項5
前記適応量子ビルダコンポーネントが共有メモリへのスレッドアクセスを監視する請求項１に記載のマルチプロセッシングシステム。
請求項6
閾数の操作が共有メモリとして指定されたメモリ以外のメモリにアクセスすると、前記適応量子ビルダコンポーネントが前記量子境界を終了させる請求項５に記載のマルチプロセッシングシステム。
請求項7
前記適応量子ビルダコンポーネントが、前記マルチスレッドアプリケーションコード内にコードを挿入(inserting)することによって、スレッドの実行を監視する請求項１に記載のマルチプロセッシングシステム。
請求項8
前記挿入された同期コードがメモリ操作を追跡(tracking)するための共有テーブル(sharing table)を含む請求項７に記載のマルチプロセッシングシステム。
請求項9
前記決定論的コンポーネントが前記決定論的順序(deterministic order)を指定するために使用されるトークン(token)を実装(implements)し、前記適応量子ビルダコンポーネントが前記トークンによって指定されたスレッドのスレッド実行(execution)を監視する請求項１に記載のマルチプロセッシングシステム。
請求項10
ハードウェアで排他的(exclusively)に実行される請求項１に記載の方法。
請求項11
ソフトウェアで排他的に実行される請求項１に記載の方法。
請求項12
ハードウェアおよびソフトウェアの組み合わせを使用して実行される請求項１に記載の方法。
請求項13
マルチスレッドアプリケーションのスレッドによって実行されるメモリ操作の順序を制御するためのマルチプロセッシングシステムにおける方法において、マルチプロセッシングシステムにおいてマルチスレッドアプリケーションコードを実行するステップであって、前記マルチスレッドアプリケーションコードが複数のスレッドを指定する、ステップと、前記マルチスレッドアプリケーションコードの前記実行を２つ以上の量子に分割するステップであって、各量子がメモリ操作を含む予め定められた数の操作から成る、ステップと、前記複数のスレッドが前記２つ以上の量子を実行する決定論的順序を指定するステップであって、前記マルチスレッドアプリケーションコードが実行されるとき、メモリ操作を指定するスレッド間(inter-thread)通信が決定論的(deterministic)である、ステップと、前記予め定められた数の操作の実行前に量子を終了(end)させるかどうかを決定するために、量子のスレッドの実行を監視するステップとを含む方法。
請求項14
トークンがスレッドの識別子(identifier)に一致(matches)するとき、前記スレッドが量子を実行するように、前記複数のスレッドが前記２つ以上の量子を実行する前記決定論的順序が前記トークンによって指定される請求項１３に記載の方法。
請求項15
スレッド実行を監視するステップが、識別子が前記トークンに一致する前記スレッドによって発行される(issued)プライベートデータへのアクセス数を追跡(tracking)するステップと、前記スレッドによって発行されたプライベートデータへのアクセス数が予め定義された(predefined)数を超えるとき、前記予め定められた数の操作の前記実行の前に前記量子を終了させるステップとを含む請求項１４に記載の方法。
請求項16
スレッド実行を監視するステップが、アプリケーションレベル同期プリミティブ(primitive)が、識別子が前記トークンに一致する前記スレッドによって解除される(released)ことの指示(indication)を受信するステップと、前記アプリケーションレベル同期プリミティブの解除に応答して、前記予め定められた数の操作の実行前に前記量子(quantum)を終了させるステップとを含む請求項１４に記載の方法。
請求項17
スレッドの実行を監視するステップが、前記マルチスレッドアプリケーションコード内に同期コードを挿入するステップを含む請求項１３に記載の方法。
請求項18
マルチプロセッシングシステムに、マルチスレッドアプリケーションのスレッドによって実行されるメモリ操作の順序を制御させることができるコードを格納するコンピュータ可読記憶媒体において、前記コードが、マルチスレッドアプリケーションコードを複数の量子に分割するためのコードであって、各量子が予め定められた数のメモリ操作から成る、コードと、前記複数の量子が実行される決定論的順序を指定するためのコードと、前記マルチスレッドアプリケーションの前記決定論的実行が前記マルチスレッドアプリケーションのクリティカルパスに従うように、スレッドが前記予め定められた数のメモリ操作の実行を終了する前に、量子を終了させるためのコードとを含むコンピュータ可読記憶媒体。
請求項19
マルチスレッドアプリケーションを配置し、前記マルチスレッドアプリケーションのスレッドによって実行されるメモリ操作の順序を制御するためのマルチプロセッシングシステムにおける方法において、マルチプロセッシングシステムにおいて実行する仮想マシン内のマルチスレッドアプリケーションコードを実行するステップであって、前記マルチスレッドアプリケーションコードが複数のスレッドを指定する、ステップと、前記マルチスレッドアプリケーションコードの前記実行を複数の量子に分割するステップであって、各量子がメモリ操作を含む予め定められた数の操作から成る、ステップと、特定のスレッドが前記複数の量子の中の量子を実行する決定論的順序を指定するステップであって、前記マルチスレッドアプリケーションコードが実行されるとき、スレッド間通信を指定するメモリ操作が決定論的に実行される、ステップと、前記仮想マシン内の前記スレッド間通信を追跡して、前記指定された決定論的順序が、特定のスレッドがクラッシュ(crash)をもたらすために観察される量子を実行する既知の順序に一致するかどうかを決定するステップと、前記指定された決定論的順序が既知の順序に一致することの決定に応答して、前記既知の順序のさらなる実行を回避(avoiding)するステップとを含む方法。
請求項20
前記既知の順序のさらなる実行を回避するステップが、特定のスレッドが前記複数の量子の中の量子を実行する新しい決定論的順序(order)を指定するステップを含む請求項１９に記載の方法。
請求項21
前記既知の順序のさらなる実行を回避するステップが、量子における前記予め定められた数の操作を変更するステップを含む請求項１９に記載の方法。
請求項22
前記変更がランダムである請求項２１に記載の方法。
請求項23
配置された(deployed)マルチスレッドアプリケーションにおける動的バグ(dynamic bug)回避(avoidance)のためのマルチプロセッシングシステムにおいて、複数のスレッドを指定する配置されたマルチスレッドアプリケーションコードと、前記コードを、それぞれ決定論的操作数(deterministic number of operations)から成る２つ以上の量子(quanta)に分割するための量子ビルダコンポーネントと、前記マルチスレッドアプリケーションのスレッドが前記２つ以上の量子を実行する決定論的順序を指定するための決定論的コンポーネントと、前記指定された決定論的順序での前記複数のスレッド間の通信を監視し、既知の並行処理のバグの実行を回避するための動的バグ回避コンポーネントであって、前記既知の並行処理のバグが、以前、前記マルチスレッドアプリケーションにクラッシュさせた前記複数のスレッド間の通信のシーケンスである、動的バグ回避コンポーネントとを含むマルチプロセッシングシステム。
請求項24
前記コードが仮想マシン内に配置される請求項２３に記載のマルチプロセッシングシステム。
請求項25
前記監視される通信が共有メモリにアクセスするメモリ操作である請求項２３に記載のマルチプロセッシングシステム。
請求項26
既知の並行処理のバグの実行が、新しい決定論的順序を指定する前記決定論的コンポーネントによって回避される請求項２３に記載のマルチプロセッシングシステム。
請求項27
既知の並行処理のバグの実行が、新しい決定論的操作数を指定し、前記コードを、前記新しい決定論的操作数をそれぞれ指定する２つ以上の量子に分割する量子ビルダコンポーネントによって回避される請求項２３に記載のマルチプロセッシングシステム。
請求項28
複数の既知の並行処理のバグを格納するローカルバグライブラリと、前記マルチスレッドアプリケーションがクラッシュしたとき、決定論的順序、および前記複数のスレッド間の通信のシーケンスを識別し、前記識別された決定論的順序および前記識別された通信のシーケンスに対応する新しい既知の並行処理のバグを含むように前記ローカルバグライブラリを更新するためのバグ報告コンポーネントとをさらに含む請求項２３に記載のマルチプロセッシングシステム。
請求項29
前記バグ報告コンポーネントが前記新しい既知の並行処理のバグに関連付けられた情報を含む更新をバグアグリゲータ(aggregator)システムに送信する請求項２８に記載のマルチプロセッシングシステム。
請求項30
前記バグ報告コンポーネントがバグアグリゲータシステムから更新を受信し、前記更新が前記マルチスレッドアプリケーションの並行処理のバグに関連付けられた情報を含み、前記バグ報告コンポーネントが前記受信された情報を含むように前記ローカルバグライブラリを更新する請求項２８に記載のマルチプロセッシングシステム。
請求項31
決定論的順序で実行される複数のスレッドを指定するマルチスレッドアプリケーションにおける並列化(parallelism)を回復(recovering)するためのマルチプロセッシングシステムにおける方法において、複数のスレッドを指定するマルチスレッドアプリケーションコードを２つ以上の量子に分割するステップであって、各量子がスレッドによって実行されるべき予め定められた数の操作から成る、ステップと、スレッドによって実行されるべき量子ごとに前記スレッドに対して証明可能(provably)にローカルであるメモリロケーションにアクセスする任意の操作を識別するステップと、前記マルチスレッドアプリケーションコード内に同期コードを挿入して、前記複数のスレッドが前記２つ以上の量子を実行する決定論的順序を指定するステップであって、前記挿入された同期コードが、前記スレッドに対して証明可能にローカルであるメモリロケーションにアクセスする前記識別された操作以外のメモリロケーションにアクセスする操作を監視するための共有メモリデータ構造を実装する、ステップとを含む方法。
請求項32
前記マルチスレッドアプリケーションコードを実行するステップと、前記スレッドが、別のスレッドに対してプライベートとして前記共有テーブルにおいて識別されるメモリロケーションにアクセスするための操作を発行するとき、前記複数のスレッドのそれぞれが実行における決定論的ポイントに到達(reaches)し、前記決定論的順序が、前記スレッドが実行を始めることを指定するまで、前記スレッドの実行を一時停止(suspending)するステップとをさらに含む請求項３１に記載の方法。
請求項33
前記スレッドが、前記スレッドに対して証明可能にローカルであるメモリロケーションにアクセスするための操作を発行(issues)するとき、前記指定された決定論的順序に関係なく前記操作を実行するステップをさらに含む請求項３２に記載の方法。
請求項34
マルチプロセッシングシステムに、マルチスレッドアプリケーションのスレッドによって実行されるメモリ操作の順序を制御させることができるコードを格納するコンピュータ可読記憶媒体において、前記コードが、マルチスレッドアプリケーションコードを複数の量子に分割するためのコードであって、各量子が予め定められた数のメモリ操作から成る、コードと、前記複数の量子が実行される決定論的順序を指定するためのコードと、単一のスレッドに対してローカルであると証明されないメモリロケーションにアクセスするメモリ操作の、異なるスレッドによる前記実行を決定論的にすると共に、前記単一のスレッドによる、前記単一のスレッドに対してローカルであると証明されるメモリロケーションにアクセスするメモリ操作の同時実行を可能にするためのコードとを含むコンピュータ可読記憶媒体。
請求項35
決定論的順序で実行される複数のスレッドを指定するマルチスレッドアプリケーションにおける並列化を回復するためのマルチプロセッシングシステムにおける方法において、複数のスレッドを指定するマルチスレッドアプリケーションコードを２つ以上の量子に分割するステップであって、各量子がスレッドによって実行されるべき予め定められた数の操作から成る、ステップと、１つまたは複数の異なるメモリロケーションごとに、前記メモリロケーションにアクセスする少なくとも１つのメモリロケーションを含む量子を構文解析するステップであって、前記メモリロケーションの少なくとも１つについて、前記量子が前記メモリロケーションにそれぞれアクセスする複数のメモリ操作を含む、ステップと、前記異なるアクセスされたメモリロケーションごとに、前記メモリロケーションにアクセスする第１に起こるメモリ操作についてのみ、同期コードが挿入される、前記マルチスレッドアプリケーションコードから結果コードを生成するステップであって、前記同期コードが、前記複数のスレッドが前記２つ以上の量子を実行する決定論的順序を指定するために使用される、ステップとを含む方法。
請求項36
前記結果コードを実行するステップをさらに含む請求項３５に記載の方法。
請求項37
マルチスレッドアプリケーションをテストするためのマルチプロセッシングシステムにおける方法において、開発コンピュータから、複数のスレッドを指定するマルチスレッドアプリケーションをテストする旨の要求を受信するステップと、前記受信された要求に関するどんな支払いもないとき、マルチスレッドアプリケーションを２つ以上の量子に分割するステップであって、各量子が前記複数のスレッドうちの１つのスレッドによって実行される予め定められた数の操作から成る、ステップと、前記複数のスレッドが前記２つ以上の量子を実行する決定論的順序を指定するステップと、前記マルチスレッドアプリケーションの複数の実行パスについて、指定された入力についてバグが存在するかどうかを実行パスごとに識別するステップと、バグが識別されないとき、前記開発コンピュータに、バグが前記マルチスレッドアプリケーションにおいて識別されなかったことの指示を送信するステップと、１つまたは複数のバグが識別されたとき、前記開発コンピュータに、１つまたは複数のバグが識別されたことの指示を送信するステップと、前記識別されたバグを所定の料金で(for a fee)明らかにすると申し出るステップとを含む方法。
請求項38
前記識別されたバグを所定の料金で(for a fee)明らかにするという前記申し出が受け入れられたことの指示を前記開発コンピュータから受信するステップと、前記識別されたバグ(bugs)を明らかにする(revealing)ステップと、をさらに含む請求項３７に記載の方法。
請求項39
前記開発コンピュータで、前記識別されたバグを再生するための機構を提供するステップをさらに含む請求項３８に記載の方法。
請求項40
新しい決定論的順序が実行パスごとに指定される請求項３７に記載の方法。
請求項41
実行パスごとに、前記マルチスレッドアプリケーションが２つ以上の量子に分割され、各量子が、前記複数のスレッドのうちの１つのスレッドによって実行される新しい所定の数の操作から成る、請求項３７に記載の方法。
請求項42
前記料金が識別されたバグの数に基づく請求項３７に記載の方法。
請求項43
コンテンツが、コンピューティングシステムに、コンピュータプログラムをテストするための方法を実行させることができるコンピュータ可読媒体であって、前記方法が、開発コンピュータから、識別されたコンピュータプログラムをテストする旨の要求を受信するステップと、前記受信された要求に関するどんな支払いもないとき、前記コンピュータプログラムによって含まれるバグを識別しようと試行する(attempt)ために、前記コンピュータプログラムをテストするステップと、バグが識別されないとき、前記開発コンピュータに、バグが前記コンピュータプログラムにおいて識別されなかったことの指示を送信するステップと、１つまたは複数のバグが識別されたとき、前記開発コンピュータに、１つまたは複数のバグが識別されたことの指示を送信するステップと、前記識別されたバグを所定の料金(a fee)で明らかにすると申し出るステップとを含むコンピュータ可読媒体。